连续子元素最大和

n^2解法

/**
* 1. 如果有连续的正数，那么只要考虑第一个。因为假设某个子串的和是最大的，但这个子串首位前一个是个正数，
* 那么这个子串加上这个正数形成的子串和会更大，产生了矛盾，因此假设不成立。
* 2. 所以最大和的子串前一位必为负数（0、或没有数）
*/
int arr[] = {8, -2, 5, 1, -4, 7, 6, -9, 1, 13};
int max = Integer.MIN_VALUE;
for (int i = 0; i < arr.length; i++) {
if (arr[i] > 0 && i > 0 && arr[i - 1] < 0 || arr[i] > 0) {
int sum = 0;
for (int j = i; j < arr.length; j++) {
sum += arr[j];
if (sum > max) {
max = sum;
}
}
}
}
System.out.println(max);

n解法（动态规划）

状态转移方程为：
MaxSum[i] = Max{ MaxSum[i-1] + A[i], A[i]}
MaxSum[i]表示下标为i及以前的序列中的连续子元素最大和
A[i]表示下标为i的元素值

int MaxSubSequence(int A[], int N) {
int ThisSum, MaxSum, j;
ThisSum = MaxSum = 0;
for (j = 0; j < N; j++) {
ThisSum += A[j];
if (ThisSum > MaxSum)
MaxSum = ThisSum;
else if (ThisSum < 0)
// 相当于前面就是一个负数了，所以舍弃（解法一第二点规则）
ThisSum = 0;
}
return MaxSum;
}