C / C ++ Chương trình cho mảng con liền kề có tổng lớn nhất?

Một mảng các số nguyên được đưa ra. Chúng ta phải tìm tổng của tất cả các phần tử kề nhau. Tổng của ai 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 nhau trong mảng.

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 (mảng, 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