leetcode 剑指 Offer 42. 连续子数组的最大和

思路： 动态规划
解释： 由于要求子数组是连续的，所以每走一步就可以确定当前位置所有子数组最大和，而走到下一步时，只需要比较 “当前这个数” 与 “这个数+上一步记录的最大和” 谁更大，将更大的数保存，这个更大的数就是当前位置所有子数组最大和。因此遍历一遍数组便可确定连续子数组最大和，时间复杂度为O(n)。

class Solution {
    public int maxSubArray(int[] nums) {
        //1.定义动态数组，代表当前位置连续子数组最大和
        int[] dp = new int[nums.length];
        //2.初始化
        dp[0] = nums[0];
        int maxSub = dp[0];
        //3.遍历递推
        for(int i=1; i<nums.length; i++){
            int temp = dp[i-1] + nums[i];
            //4.状态转移
            if(temp > nums[i]) dp[i] = temp;
            else dp[i] = nums[i];
            maxSub = maxSub > dp[i] ? maxSub : dp[i];
        }
        return maxSub;
    }
}

本题同【53. 最大子数组和】
另一种解法是分治法，待补充…