LeetCode 53 最大子数组和 - 贪心解法
https://leetcode.cn/problems/maximum-subarray/description/
思路
暴力
穷举所有子数组，计算和。
- 外层遍历
index，内层遍历len。 - 最内层再计算
index到index + len的区间和。 - 这个最内层可以继续优化掉。
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int res=INT_MIN;
for(int index =0;index<nums.size();index++){
for(int len = 0;len+index<nums.size();len++){
int sum = 0;
for(int j = index;j<=index+len;j++){
sum+=nums[j];
}
res = max(sum,res);
}
}
return res;
}
};
优化后：
class Solution {
public:
int maxSubArray(vector<int> &nums) {
int res = INT_MIN;
for (int index = 0; index < nums.size(); index++) {
int sum =0;
for (int len = 0; len + index < nums.size(); len++) {
sum+=nums[index+len];
res = max(sum,res);
}
}
return res;
}
};