动态规划—最大连续子序列

具体思想是将序列分割成很多个子序列，每个子序列开头的数都是整数，那么这些子序列都是候选最优解，然后计算每个子序列的数值和ThisSum比较出最大的MaxSum就是最终的最优解。

public class CB {

    public static void main(String[] args) {
        int[] data = new int[]{-2, 11, -455, 13, -5, -2, 222};
        System.out.println(MaxSubSequence(data));
    }

    static int MaxSubSequence(int A[]) {
        int N = A.length;
        int ThisSum = 0, MaxSum = 0, start = 0, end = 0;
        for (int j = 0; j < N; j++) {
            ThisSum += A[j];
            if (ThisSum > MaxSum) {
                end = j;
                MaxSum = ThisSum;
            } else if (ThisSum < 0) {
                if (j + 1 < A.length) {
                    start = j + 1;
                }
                ThisSum = 0;
            }
        }
        System.out.println(start + "   " + end);
        return MaxSum;
    }
}

最终输出是：

3   6
228

即从下标3开始到下标6结束之间的子序列就是最优解。