题目链接:
题目描述:
给你一个整数数组 nums
,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
子数组 是数组中的一个连续部分。
示例 1:
输入:nums = [-2,1,-3,4,-1,2,1,-5,4]
输出:6
解释:连续子数组 [4,-1,2,1] 的和最大,为 6
最近刷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;
}
};