【试题描述】输入一个整型数组，数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。
求所有子数组的和的最大值。要求时间复杂度O(n)。
【试题来源】未知
【参考代码】
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| int findGreastestSumOfSubArray(int array[], int n) {
if(array == NULL || n <= 0) {
throw ("Invalid Inptut.");
}
int *dp = new int[n];
int maxSum = array[0];
for(int i = 0; i < n; i++) {
if(i == 0 || dp[i - 1] <= 0) {
dp[i] = array[i];
} else if(i > 0 && dp[i - 1] > 0){
dp[i] = dp[i - 1] + array[i];
}
if(dp[i] > maxSum) {
maxSum = dp[i];
}
}
return maxSum;
}
|