题目

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

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4]

输出: 6

解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

思路：

定义：

    sum：累加和

    max：和的最大值

遍历数组nums

1.nums[i] 赋给sum

2.如果sum<0，则sum保留原值，否则下一个元素的值 加上 sum

3.如果sum > max,则 max = sum，更新sum

代码：

    public int maxSubArray(int[] nums) {

        int max = nums[0];

        int sum = nums[0];

        for (int i = 1; i < nums.length; i++) {

            if (sum >= 0)

                sum = nums[i] + sum;

            else

                sum = nums[i];

            if (sum > max)

                max = sum;

        }

        return max;

    }

总结

动态规划题