月度归档： 2020 年 10 月

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

初看有点懵逼，一直想有啥简单的解法，想半天只想到用暴力做orz

时间复杂度 O(n^3) 时间爆炸

class Solution {
    public int maxSubArray(int[] nums) {
        int max = -100;
        int sum = 0;
        if(nums.length == 1){
            return nums[0];
        }
        for(int i = 0;i < nums.length; i++){
            for(int j = i ; j < nums.length; j++){
                sum = 0;
                for(int k = i ; k <= j ; k++ ){
                    sum += nums[k];
                    if(sum > max){
                        max = sum;
                    }
                }
            }
        }
        return max;
    }
}

贪心法 相对于暴力简直快的飞起

贪心准则：遍历整个数组，逐一求和sum.当sum <= 0 时，对后续子序列和不是正收益，直接舍弃,同时用max记录sum的最大值.

class Solution {
    public int maxSubArray(int[] nums) {
        int max = -2147483648;//避免干扰设置成最小
        int sum = 0;
        for(int i : nums){
            if(sum > 0){
                sum += i;
            }else{
                sum = i;
            }
            max = max > sum ? max : sum;
            
        }
        return max;
    }
}

学习了大佬们给出的动态规划法 感觉跟贪心法一个思路，只不过是把sum求和结果放在nums上了

class Solution {
    public int maxSubArray(int[] nums) {
        int point = nums[0];
        for(int i = 1;i < nums.length;i++){
            if(point > 0 ){
                nums[i] += point;
            }
            point = nums[i];
        }
        return Arrays.stream(nums).max().getAsInt();
    }
}