[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 dp = new ArrayList();
    dp.add(nums[0]);
    for(int i=1;i0){
            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 res){
            res = dp.get(i);
        }
    }
    return res;
}