Maximum Subarray
要记录以下三个值:
sum = 0;
maxsubarray_sum = INTMIN;
minsum = 0;
code
class Solution {
public:
/**
* @param nums: A list of integers
* @return: A integer indicate the sum of max subarray
*/
int maxSubArray(vector<int> nums) {
// write your code here
if(nums.size() == 0)
{
return -1;
}
int sum = 0;
int minsum = 0;
int ret = numeric_limits<int>::min();
for(int i = 0; i<nums.size(); i++)
{
sum += nums[i];
ret = max(ret, sum-minsum);
minsum = min(minsum, sum);
}
return ret;
}
};