Skip to content

Instantly share code, notes, and snippets.

@qiaoxu123
Last active March 16, 2019 11:59
Show Gist options
  • Save qiaoxu123/2add959372514f31514edc72f2630d3b to your computer and use it in GitHub Desktop.
Save qiaoxu123/2add959372514f31514edc72f2630d3b to your computer and use it in GitHub Desktop.
> 经典的动态规划题目 第一种方法是采用从头进行相加的方法进行,当总和小于等于0时,将之前的数记为最大值。重复判断即可。 缺点:复杂度很高 第二种方法:使用一个循环实现,但效率上还是没有提高。。
//Runtime: 16 ms, faster than 20.14%
//Memory Usage: 10.3 MB, less than 60.30%
class Solution {
public:
int maxSubArray(vector<int>& nums) {
if(nums.empty()) return NULL;
if(nums.size() == 1) return nums[0];
int sum = 0;
int maxSum = INT_MIN;
for(int i = 0;i < nums.size();++i){
for(int j = i;j < nums.size();++j){
if(sum >= 0){
sum += nums[j];
if(sum >= maxSum)
maxSum = sum;
}
else
break;
// cout << "nums = " << nums[j] << endl;
// cout << "maxSum = " << maxSum << " "<< "sum = " << sum << endl;
// cout << "-------" << endl;
}
sum = 0;
}
return maxSum;
}
};
//Runtime: 16 ms, faster than 20.14%
//Memory Usage: 10.4 MB, less than 40.32%
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int sum = nums[0],maxSum = sum;
for(int i = 1;i < nums.size();++i){
sum = max(nums[i],(sum + nums[i]));
maxSum = max(sum,maxSum);
}
return maxSum;
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment