정수 배열이 제공됩니다. 출력으로 보낼 연속된 모든 요소의 합이 가장 큰 합을 찾아야 합니다.
동적 프로그래밍을 사용하여 현재 기간까지의 최대 합계를 저장합니다. 배열에서 연속 요소의 합계를 찾는 데 도움이 됩니다.
입력 및 출력
Input: An array of integers. {-2, -3, 4, -1, -2, 1, 5, -3} Output: Maximum Sum of the Subarray is: 7
알고리즘
maxSum(array, 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