Mảng con liền kề có tổng lớn nhất

Một mảng các số nguyên được cung cấp. Chúng ta phải tìm tổng của tất cả các phần tử kề nhau, có tổng lớn nhất, sẽ được gửi dưới dạng đầu ra.

Sử dụng lập trình động, chúng tôi sẽ lưu trữ tổng lớn nhất cho đến hạn hiện tại. Nó sẽ giúp tìm tổng cho các phần tử liền kề trong mảng.

Đầu vào và Đầu ra

Input:
An array of integers. {-2, -3, 4, -1, -2, 1, 5, -3}
Output:
Maximum Sum of the Subarray is: 7

Thuật toán

maxSum(array, n)

Đầu vào - Mảng chính, kích thước của mảng.

Đầu ra - tổng tối đa.

Begin
   tempMax := array[0]
   currentMax = tempMax
   for i := 1 to n-1, do
      currentMax = maximum of (array[i] and currentMax+array[i])
      tempMax = maximum of (currentMax and tempMax)
   done
   return tempMax
End

Ví dụ

#include<iostream>
using namespace std;

int maxSum( int arr[], int n) {
   int tempMax = arr[0];
   int currentMax = tempMax;

   for (int i = 1; i < n; i++ ) { //find the max value
      currentMax = max(arr[i], currentMax+arr[i]);
      tempMax = max(tempMax, currentMax);
   }
   return tempMax;
}

int main() {
   int arr[] = {-2, -3, 4, -1, -2, 1, 5, -3};
   int n = 8;
   cout << "Maximum Sum of the Sub-array is: "<< maxSum( arr, n );
}

Đầu ra

Maximum Sum of the Sub-array is: 7