leetcode 53. 最大子数组和-Toy模板网

这篇具有很好参考价值的文章主要介绍了leetcode 53. 最大子数组和。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

2023.7.28

leetcode 53. 最大子数组和,leetcode专栏,leetcode,算法,职场和发展,c++,数据结构

要求找最大和的连续子数组，我的思路是用一个temp记录局部最优值，用ans记录全局最优值。然后在每次for循环进行一个判断：当前遍历元素+temp值是否大于当前遍历元素的值，如果大于，说明temp值是帮了正忙的，所以让temp += 当前元素值；如果小于，说明temp是帮了倒忙的，此时让temp = 当前元素值。 再更新全局最优值。

下面看代码：

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int ans = nums[0];
        int temp = nums[0];
        for(int i=1; i<nums.size(); i++)
        {
            if(temp + nums[i] > nums[i]) temp += nums[i];
            else temp = nums[i];

            if(temp > ans) ans = temp;
        }
        return ans;
    }
};

2023.8.25

本题也可以用动态规划做。直接上代码：

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if(nums.size() == 1) return nums[0];
        vector<int> dp(nums.size());
        dp[0] = nums[0];
        int ans = nums[0];
        for(int i=1; i<nums.size(); i++)
        {
            dp[i] = max(dp[i-1]+nums[i] , nums[i]);
            ans = max(ans,dp[i]);
        }
        return ans;
    }
};

2023.10.8

三刷。还是动态规划思想，用java代码：文章来源地址https://www.toymoban.com/news/detail-613002.html

class Solution {
    public int maxSubArray(int[] nums) {
        int max_sum = nums[0];
        int[] dp = new int[nums.length]; //dp[i]代表以nums[i]结尾的最大子数组和。
        dp[0] = nums[0];
        for(int i=1; i<dp.length; i++){
            if(dp[i-1] <= 0){
                dp[i] = nums[i];
            }
            else{
                dp[i] = nums[i]+dp[i-1];
            }
            max_sum = Math.max(max_sum,dp[i]);
        }
        return max_sum;
    }
}

到了这里，关于leetcode 53. 最大子数组和的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！