动态规划_最大连续子序列和

package com.zmy.ds;

import java.util.Scanner;

public class Mcss {
    public static void main(String[] args) {
        int maxn = 10010;

        int[] A = {-2, 11, -4, 13, -5, -2};
        int[] dp = new int[maxn];
        int n = A.length;

        dp[0] = A[0]; //只有一个数,单独处理
        for (int i = 1; i < n; i++) {
            dp[i] = Math.max(A[i], dp[i - 1] + A[i]);
        }

        // 找dp[]中最大值,方法一
//        int k = 0;
//        for (int i = 1; i < n; i++) {
//            if (dp[i] > dp[k]) {
//                k = i;
//            }
//        }

        // 找dp[]中最大值,方法二
        int max = dp[0];
        for (int i = 1; i < n; i++) {
            if (dp[i] > max) {
                max = dp[i];
            }
        }
        System.out.println(max);
//        System.out.println(dp[k]);
    }
}