[Java] 最大子序和，给定一个整数数组，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

• 目的
• 分析
• 代码

目的

练习与动态规划的相关问题

分析

1. 无需考虑i、i-1、i-2通过分治的思想，考虑i和i-1之间的关系即可
2. 定义一个集合dp用于存放子串和的结果集，dp数组表示以i结尾的最大字串的和的集合
3. 求出dp集合中的最大值即可

代码

public int maxSubArray(int[] nums) {
    if(nums.length == 1){
        return nums[0];
    }
    ArrayList<Integer> dp = new ArrayList<Integer>();
    dp.add(nums[0]);
    for(int i=1;i<nums.length;i++){
        if(dp.get(i-1)>0){
            Integer tem = dp.get(i-1) + nums[i];
            dp.add(tem);
        }else{
            dp.add(nums[i]);
        }
    }
    int res = dp.get(0);
    for(int i=1;i<dp.size();i++){
        if(dp.get(i) > res){
            res = dp.get(i);
        }
    }
    return res;
}