給定一個 10 個元素的陣列,請找出最大的連續子陣列和,所有子陣列加總會在 -1e8 到 1e8 之間。
輸入:1 2 3 4 5 -10 20 30 -40 10
輸出:55
#include <iostream>
using namespace std;
int divide(int L, int R);
int conquer(int L, int M, int R);
int a[10+5];
int main(){
for(int i=0; i<10; i++)
cin >> a[i];
cout << divide(0, 9) << '\n';
}
int divide(int L, int R){
if(L == R) return a[L];
int maxL, maxR, maxLR, M=(L+R)/2;
maxL = divide(L, M);
maxR = divide(M+1, R);
maxLR = conquer(L, M, R);
return max(maxL, max(maxR, maxLR));
}
int conquer(int L, int M, int R){
int sumL=0, sumR=0, maxL=-1e8, maxR=-1e8;
for(int i=L; i<=M; i++){
sumL += a[i];
if(sumL > maxL) maxL = sumL;
}
for(int i=M+1; i<=R; i++){
sumR += a[i];
if(sumR > maxR) maxR = sumR;
}
return max(maxL, max(maxR, maxL+maxR));
}