최대 합 연속 하위 배열을 위한 C/C++ 프로그램?

정수 배열이 제공됩니다. 인접한 모든 요소의 합을 찾아야 합니다. 합계가 가장 큰 쪽이 출력으로 전송됩니다.

동적 프로그래밍을 사용하여 현재 기간까지의 최대 합계를 저장합니다. 배열의 연속 요소에 대한 합을 찾는 데 도움이 됩니다.

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

알고리즘

최대합(배열, n)

입력 - 기본 배열, 배열의 크기입니다.

출력 - 최대 합계.

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

예시

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

출력

Maximum Sum of the Sub-array is: 7