算法题库学习-最大子序和

题目

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

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：

输入：nums = [1]
输出：1

示例 3：

输入：nums = [0]
输出：0

示例 4：

输入：nums = [-1]
输出：-1

示例 5：

输入：nums = [-100000]
输出：-100000

提示：

• 1 <= nums.length <= 3 * 104
• -105 <= nums[i] <= 105

解法

解法一： 双指针的方式解决，但是这种是暴力解法，较为复杂，不推荐。

class Solution {

    // 暴力解决，但是较为复杂，不推荐
    public int maxSubArray(int[] nums) {
        if(nums == null || nums.length == 0){
            return 0;
        }
        if(nums.length == 1){
            return nums[0];
        }
        int maxSum = 0;
        int tmp = 0;
        int sum = 0;
        for(int i = 0 ; i < nums.length ; i++){
            sum = sum + nums[i];
            if(i == 0 || sum > maxSum){
                maxSum = sum;
            }
            for(int j = i + 1 ; j < nums.length ; j++){
                sum = sum + nums[j];
                if(sum > maxSum){
                    maxSum = sum;
                }
            }
            sum = 0;
        }
        return maxSum;
    }
    
}

解法二： 贪心算法

把第一项值赋值给result和sum，result存的总是最大和，遍历数组，每次都先判断sum是否大于0（如果大于0，说明对于nums[i]是增益的）这个时候 sum += nums[i] ， 如果sum小于0（说明sum加上nums[i]还没有nums[i]大），这时候 sum = nums[i]，每次都要判断result和sum的大小。

class Solution {
    // 贪心法，把第一项值赋值给result和sum，result存的总是最大和，遍历数组，每次都先判断sum是否大于0（如果大于0，说明对于nums[i]是增益的）这个时候 sum += nums[i] ， 如果sum小于0（说明sum加上nums[i]还没有nums[i]大），这时候 sum = nums[i]，每次都要判断result和sum的大小。
    public int maxSubArray(int[] nums) {
        if(nums == null || nums.length == 0){
            return 0;
        }
        int sum = nums[0];
        int result = sum;
        for(int i = 1 ; i < nums.length ; i++){
            if(sum > 0){
                sum += nums[i];
            }else {
                sum = nums[i];
            }
            result = Math.max(result,sum);
        }
        return result;
    }
}

总结

本篇文章讲解了算法题目的思路和解法，代码和笔记由于纯手打，难免会有纰漏，如果发现错误的地方，请第一时间告诉我，这将是我进步的一个很重要的环节。以后会定期更新算法题目以及各种开发知识点，如果您觉得写得不错，不妨点个关注，谢谢。

本文地址：https://blog.csdn.net/weixin_45124488/article/details/113973910