1.暴力求解法
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n = nums.size();
int ans = INT_MIN;
for (int i = 0; i < n; i++){
for (int j = i; j < n; j++){
int sum = 0;
for (int k = i; k <= j; k++){
sum += nums[k];
}
if(sum > ans){
ans = sum;
}
}
}
return ans;
}
};
2.优化枚举（动态规划）法
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n = nums.size();
int ans = INT_MIN;
for (int i = 0; i < n; i++){
int sum = 0;
for (int j = i; j < n; j++){
sum += nums[j];
if(sum > ans){
ans = sum;
}
}
}
return ans;
}
};
3.贪心法
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n = nums.size();
int ans = INT_MIN;
int sum = 0;
for (int i = 0; i < n; i++){
sum += nums[i];
if(sum > ans){
ans = sum;
}
if (sum < 0){
sum = 0;
}
}
return ans;
}
};
4.分治法
