以leetcode上“最大子数组和”为例详解贪心算法

题目链接:

力扣

题目描述:

给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

子数组 是数组中的一个连续部分。

示例 1:

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

最近刷leetcode这道题的时候,刚开始直接暴力循环求解,结果超出时间限制。

以leetcode上“最大子数组和”为例详解贪心算法自己学习了官方题解的第一种办法:贪心算法。跟大家分享一下自己的心得体会。

百度给出的贪心算法算法思路:

贪心算法一般按如下步骤进行: 

①建立数学模型来描述问题  

②把求解的问题分成若干个子问题 

③对每个子问题求解,得到子问题的局部最优解  

④把子问题的解局部最优解合成原来解问题的一个解  

问题分解:这里把整数数组的最大子数和分解成,以nums[i]结尾的数组的最大子数组之和。

子问题求解:对每个以num[i]为结尾的数组的最大子数组之和有,若当前指针所指的元素之前的和小于0,就丢掉当前元素之前的数列。

全局最优解:这些nums[i]的最大子数组和的最大值。

策略:若当前指针所指元素之前的和小于0,则丢弃当前元素之前的数列。

代码实现:

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int max_sum = INT_MIN; 
        int pre = 0;
        // pre = pre < 0 ? x : pre + x的操作是求局部最优解
        // max_sum = max(x, max_sum);是全局求解
        for(auto& x : nums) {
            if (pre < 0) {
                max_sum = max(x, max_sum); // 全局求解
                pre = x;
            } else {
                max_sum = max(pre + x, max_sum); 
                pre = pre + x;
            }
        }
        return max_sum;
    }
};

上一篇:leetcode92 反转链表II


下一篇:LeetCode92-反转链表Ⅱ