Chương trình mảng con tối đa trong Python

Mã Python

Chạy

def find[arr, l]:
    max_sum = -1
    ans = []
    for i in range[l]:
        for j in range[i, l]:
            a = sum[array[i:j + 1]]
            if a > max_sum:
                max_sum = a
                ans = array[i:j + 1]

    print["Sub array which will give maximum sum", ans]
    print["Maximum sum = ", max_sum]


array = [-1, 8, 1, -7, -1, 5, 1, -3]
print["Array =", array]
find[array, len[array]]

đầu ra

Array = [-1, 8, 1, -7, -1, 5, 1, -3]
Sub array which will give maximum sum [8, 1]
Maximum sum = 9

Trong mảng con liền kề tối đa trong Python, bạn được cung cấp một danh sách các số nguyên [dương và âm] và bạn phải tìm một danh sách con từ danh sách đã cho có tổng tối đa và in tổng

Ví dụ. list = [1, 6, -7, 5]
hiện tại, các danh sách liền kề có thể có là.
[1]
[1, 6]
[1, 6, -7]
[1, 6, -7, 5]
[6]
[6, -7]
[6, -7, 5]
[-7]
[-7, 5]
[5]

Bây giờ, danh sách có tổng cao nhất là danh sách thứ 2 có tổng là 7

Bây giờ, hãy viết mã bài toán mảng con tối đa

Mã cho mảng con liền kề tối đa trong Python

myList = [-1, 2, 4, -7, 5, -9]
listOfSubLists = []
for i in range[len[myList]+1]:
    for j in range[i+1, len[myList]+1]:
        listOfSubLists.append[myList[i:j]]
listOfAllSum = []
for i in listOfSubLists:
    listOfAllSum.append[sum[i]]
max = -1
index = 0
for i in range[len[listOfAllSum]]:
    if listOfAllSum[i]>max:
        max = listOfAllSum[i]
        index = i
print['List with maximum sum is: ', listOfSubLists[index]]
print['Maximum sum is: ', max]

đầu ra

Hơn 100 dự án Python tốt nhất với mã nguồn

cũng đọc

• Dấu nối các chữ cái trong Python
• Động đất trong Python. Tính toán dễ dàng
• Hình chữ nhật sọc trong Python
• Các từ vuông góc trong Python
• Giao hàng miễn phí bằng Python
• Raj đã đặt hàng hai mặt hàng điện tử Python. chuyên gia phân công
• Điểm nhóm trong Python
• Bán vé tại Sân vận động Cricket bằng Python. chuyên gia phân công
• Tách câu trong Python
• Cắt chuỗi trong JavaScript
• Chữ số đầu tiên và chữ số cuối cùng trong Python. chuyên gia phân công
• Danh sách lập chỉ mục trong Python
• Định dạng ngày trong Python. chuyên gia phân công
• Đếm ngược năm mới trong Python
• Thêm hai đa thức trong Python
• Tính tổng các số chẵn trong Python. chuyên gia phân công
• Chẵn và Lẻ trong Python
• Trò chơi viết thư bằng Python
• Tổng các số không nguyên tố trong Python
• Số bị thiếu nhỏ nhất trong Python
• Xoay chuỗi trong Python
• Thông điệp bí mật trong Python
• Trộn từ trong Python
• Số có một chữ số trong Python
• Chuyển số trong Python. chuyên gia phân công
• Cuối tuần trong Python
• Chuyển số trong Python. chuyên gia phân công
• Chuyển đổi nhiệt độ trong Python
• Ký tự đặc biệt trong Python
• Tổng các số nguyên tố trong đầu vào trong Python

Đây là một vấn đề lập trình động, ngay cả với suy nghĩ đó, rất dễ bị vấp phải vấn đề này. Như với hầu hết các bài toán DP, bạn tạo một mảng để theo dõi các giá trị mà bạn tính toán. Đối với vấn đề này, đó sẽ là tổng của các mảng con. Tất nhiên, có giải pháp brute force, O[n²], trong đó bạn sử dụng vòng lặp for lồng nhau và tính từng tổng đơn lẻ, nhưng giải pháp DP là O[n] và ít dòng mã hơn. Hiểu giải pháp brute force là tốt trong trường hợp người phỏng vấn nói rằng bạn có thời gian vô hạn nhưng chỉ có không gian cho 1 biến nữa, tổng tối đa [đây là giả thuyết và có thể sẽ không xảy ra]. Tiếp tục giải pháp DP, bạn cần mảng có cùng độ dài với số và tổng tối đa để theo dõi để trả về. Đối với mỗi phần tử của mảng, nó sẽ bằng tổng lớn hơn của tổng trước đó cộng với phần tử hiện tại của nums hoặc chỉ phần tử hiện tại của nums. Sau đó, tổng tối đa sẽ được cập nhật thành giá trị tối đa của chính nó và tổng mới được tính này. Khi mảng nums đã được lặp lại, hãy trả về tổng tối đa

Giải pháp Brute Force — O[n²]

Giải pháp này trên LeetCode sẽ vượt quá giới hạn thời gian, nhưng sẽ hoạt động. Tôi chỉ đặt nó ở đây để được nhìn thấy. Trước tiên, hãy lưu độ dài của mảng nums chỉ để tăng một chút thời gian. Sau đó kiểm tra các trường hợp góc, nếu độ dài là 1 thì chỉ cần trả về một phần tử đó. Sau đó, đặt tổng tối đa cho phần tử đầu tiên của mảng. Sau đó, lặp qua mảng từ 0 đến độ dài của nums trừ 1 và tạo một biến tổng hiện tại và đặt nó thành nums[i], sau đó sử dụng vòng lặp for lồng nhau lặp lại từ i + 1 đến độ dài của nums. Thêm nums[j] vào tổng hiện tại và đặt tổng tối đa thành giá trị tối đa của chính nó, tổng hiện tại và nums[j]. Khi các vòng lặp for kết thúc, hãy trả về tổng tối đa

class Solution:
 def maxSubArray[self, nums: List[int]] -> int:
  len_n = len[nums]  if len_n == 1:
   return nums[0]
 
  max_sum = nums[0]
 
  for i in range[len_n — 1]:
   curr_sum = nums[i]
 
  for j in range[i + 1, len_n]:
   curr_sum += nums[j]
   max_sum = max[max_sum, curr_sum, nums[j]]
 
  return max_sum

Giải pháp lập trình động — O[n]

Một lần nữa, vì độ dài của mảng nums sẽ được sử dụng nhiều lần, hãy lưu nó vào một biến. Sau đó kiểm tra các trường hợp góc, nếu độ dài là 1 thì trả về phần tử duy nhất trong mảng. Sau đó tạo một mảng để giữ các khoản tiền. Sau đó nối thêm phần tử đầu tiên của nums, vì phần tử 0 sẽ luôn là chính nó. Sau đó đặt tổng tối đa thành giá trị đó. Sau đó, lặp lại từ 1 đến độ dài của nums và trong vòng lặp for này, hãy thêm giá trị tối đa của tổng trước đó cộng với nums[i] và chỉ nums[i]. Sau đó đặt tổng tối đa thành giá trị tối đa của chính nó và tổng hiện tại [sums[i]]. Sau khi hoàn thành việc lặp qua vòng lặp này, hãy trả về tổng tối đa

Là tối đa subarray động lập trình?

Làm cách nào để in mảng con trong Python?