Maximum Subarray Algorithm
算法导论4.2-5提供了一种线性时间内解决的方法。
思路是，最大子串有一个特性，从前向后逐个累加，过程中和始终为正。这是因为如果计算到某个数，和为负，则去掉包括这个数的前面这部分，剩下的子串和会更大，这和之前认为的最大子串是冲突的。
因此从前往后逐个累加求和，如果和为负，则从下一个开始重新累加。在这个过程中找出和的最大值即可。
package cpt4;
import Utils.P;
public class Ex1s5 {
/**
* find max subarray in O(n)
* @param array
* @return max < 0 means all are negative. max = 0 means all are zero.
*/
public static int[] maxSubarray(int[] d) {
int max = Integer.MIN_VALUE;
int start = 0, end = 0, tempStart = 0;
int count = 0;
for (int i = 0; i < d.length; i++) {
count += d[i];
if (count < 0) {
count = 0;
tempStart = i + 1;
} else if (count > max) {
max = count;
start = tempStart;
end = i;
}
}
return new int[] { start, end, max };
}
public static void main(String[] args) {
int[] d = { 13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15,
-4, 7 };
P.rintln(maxSubarray(d));
}
}
早晨上班路上，想起来这个算法的正确性靠前面一条特性无法保证。查了下确实还需要另一个结论。http://blog.csdn.net/joylnwang/article/details/6859677
