给定一个整数数组，找出总和最大的连续数列 博客分类： 算法题 最大的连续数列java动态规划

题目：https://leetcode-cn.com/problems/contiguous-sequence-lcci

给定一个整数数组，找出总和最大的连续数列，并返回总和。

 

示例：

 

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

输出： 6

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

 

解题：

用变量去记录连续数列总和的最大值。

用另一个变量记录当前位置可累积到的总和，若该值需大于0，否则置为0。（此处就是用了动态规划的思想）

即：f(n)=max(f(n-1)+n,0)

 

 

class Solution {
    public int maxSubArray(int[] nums) {
        if(nums==null || nums.length==0){
            return 0;
        }
        int max=nums[0];
        int dp=0;
        for(int i=0;i<nums.length;i++){
            int tmp=dp+nums[i];
            max=Math.max(tmp,max);
            dp=tmp>0?tmp:0;
        }
        return max;
    }
}