Java输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。 要求时间复杂度为O(n)。输入: nums = [-2,1,-3,4,-1,2,1,-5,4] 输出:

By CaesarChang 合作: root121toor@gmail.com

~关注我 带你看更多精品知识

见注释 简单动态规划问题 将前面的数之和做一个更新

代码语言：javascript复制

class Solution {
    public int maxSubArray(int[] nums) {
        int Max=nums[0];
        int pre=0;  //记录前面的和
        int cur=0;   //记录当前数
        for(int num:nums){
            cur=num;
            if(pre>0){  //如果前面的和>0,当前数字 前面的和
                cur =pre;
            }
            if(cur>Max){
                Max=cur;
            }
            pre=cur;   //更新前面的和
        }
        return Max;
    }
}

com gmail 动态规划

0 人点赞