题目描述：(剑指offer原题31)
https://leetcode.com/problems/maximum-subarray/
解决方法：
optim_code(c++):
运行时间12ms:
class Solution {
public:
int maxSubArray(vector<int>& nums) {
if(nums.empty())
return 0;
int nCurSum = 0 ;
int nGreatestSum = INT32_MIN;
for( int i = 0;i< nums.size();i++){
if(nCurSum<=0){
nCurSum = nums.at(i);
}else{
nCurSum += nums.at(i);
}
if(nCurSum > nGreatestSum)
nGreatestSum = nCurSum;
}
return nGreatestSum;
}
};
运行时间8ms：
class Solution {
public:
int maxSubArray(vector<int>& nums) {
if(nums.empty())
return 0;
int nCurSum = 0 ;
int nGreatestSum = INT32_MIN;
for( int i = 0;i< nums.size();i++){
nCurSum = max(nums.at(i), nCurSum +nums.at(i));
nGreatestSum = max(nCurSum, nGreatestSum);
}
return nGreatestSum;
}
};
运行时间4ms：
class Solution {
public:
int maxSubArray(vector<int>& nums) {
if(nums.empty())
return 0;
int res = nums[0], sum = res;
for(int i = 1; i < nums.size(); i++) {
sum = sum > 0 ? sum+nums[i]: nums[i];
res = max(sum,res);
}
return res;
}
};
心得：
以上解法，思路都是一样的，但是算法书写形式影响效率
内置函数max，比手动判断效率要高，当然if判断并不是得到最大值的最优方法
三目运算表达式比max函数效率高
