53. Maximum Subarray

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

题目

求数组中连续的几个数加起来最大的和。

思路

从第一个开始加，如果第一个数是正数，算一算它加第二个数等于多少，如果第一个数是负数，那就不要第一个数了，从第二个数开始加。如果头两个数的和为正数，那么算一算它加上第三个数是多少，如果头两个数的和是负数，那就从第三个数开始算。以此类推，我们每次都记录一下累加的和，它为正数就继续加，为负数就抛弃，从下一个开始。不过抛弃前先记录一下为正数时的值，最后遍历完了，这个值就是记录的最大值。

代码

 public int maxSubArray2(int[] nums) {
            int dp=nums[0];//用来计算累加和
            int max=dp;
            for (int i = 1; i < nums.length; i++) {
                if (dp>0) {
                    dp=dp+nums[i];
                }else {
                    dp=nums[i];
                }
                max=Math.max(dp, max);
            }
            return max;

        }