Last active
March 16, 2019 11:59
-
-
Save qiaoxu123/2add959372514f31514edc72f2630d3b to your computer and use it in GitHub Desktop.
> 经典的动态规划题目 第一种方法是采用从头进行相加的方法进行,当总和小于等于0时,将之前的数记为最大值。重复判断即可。
缺点:复杂度很高 第二种方法:使用一个循环实现,但效率上还是没有提高。。
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//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; | |
} | |
}; |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//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