문제 설명
양수 및 음수 배열이 주어지면 해당 배열의 최대 하위 배열 합계를 찾으십시오.
예시
입력 배열이 − {-12, -5, 4, -1, -7, 1, 8, -3}이면 출력은 9입니다.
알고리즘
-
입력 배열의 접두사 합을 계산합니다.
-
초기화- min_prefix_sum =0, res =-무한
-
i =0에서 n에 대한 루프를 유지합니다. (n은 입력 배열의 크기입니다).
-
cand =prefix_sum[i] – 미니
-
할 수 있고 res보다 크면(지금까지의 최대 하위 배열 합계), res를 그대로 업데이트합니다.
-
prefix_sum[i]이 min_prefix_sum(지금까지의 최소 접두사 합계)보다 작으면 prefix_sum[i]으로 min_prefix_sum을 업데이트합니다.
-
-
반환 해상도
예시
#include <bits/stdc++.h>
using namespace std;
int maximumSumSubarray(int *arr, int n){
int minPrefixSum = 0;
int res = numeric_limits<int>::min();
int prefixSum[n];
prefixSum[0] = arr[0];
for (int i = 1; i < n; i++) {
prefixSum[i] = prefixSum[i - 1] + arr[i];
}
for (int i = 0; i < n; i++) {
res = max(res, prefixSum[i] - minPrefixSum);
minPrefixSum = min(minPrefixSum, prefixSum[i]);
}
return res;
}
int main(){
int arr[] = {-12, -5, 4, -1, -7, 1, 8, -3};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Result = " << maximumSumSubarray(arr, n) <<endl;
return 0;
} 출력
위의 프로그램을 컴파일하고 실행할 때. 다음 출력을 생성합니다 -
Result = 9