Chương trình C/C++ cho Tổng lớn nhất của dãy con liên tiếp

Một mảng số nguyên được cho. Chúng ta phải tìm tổng của tất cả các phần tử liên tiếp. Tổng lớn nhất sẽ được gửi làm đầu ra.

Sử dụng quy hoạch động chúng ta sẽ lưu tổng lớn nhất đến số hạng hiện tại. Nó sẽ giúp tìm tổng cho các phần tử liên tiếp 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(array, n)

Input - Mảng chính, kích thước mảng.

Output - tổng lớn nhất.

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 );
}

Kết quả

Maximum Sum of the Sub-array is: 7