题目
Find the contiguous subarray within an array (containing at least one number) which has the largest sum. For example, given the array [-2,1,-3,4,-1,2,1,-5,4],the contiguous subarray [4,-1,2,1] has the largest sum = 6.
More practice:If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
解析
寻找一个子串，使其之和最大。如果存在正数，那肯定从正数开始的子串之和比较大，这里使用的贪心法，依次计算，如果当前子串的和小于0，那么就放弃重新开始计算。如果数组中全是负数，就挑选一个相对较大的负数返回即可。
这里注意寻找最大值时的界限-2147483647，测试数据里面有该值。
int maxSubArray(int* nums, int numsSize) {
int ans=-2147483647,temp=0;
for(int i=0;i<numsSize;i++)
{
if(temp+nums[i]>0)
{
temp=temp+nums[i];
if(temp>ans)
ans=temp;
}
else
{
temp=0;
}
}
for(int i=0;i<numsSize;i++)
{
if(nums[i]>ans)
ans=nums[i];
}
return ans;
}
