leetcode-53-maximum-subarray

题目

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

1
2
3
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Follow up:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

分析

这道题一开始的时候太大意了,忽略了很多的问题,当然这个

错误分析

错误的理解题目的意思是求数组中的最大的和,因而答案就有点微妙了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include "stdio.h"
int maxSubArray(int* nums, int numsSize) {
int temp=0;
int sum=0;
if(numsSize==1)
{
return nums[0];
}
else
{
for(int i=0;i<numsSize;i++)
{
for(int j=i;j<numsSize;j++)
{
if(nums[i]<nums[j])
temp=nums[i];
nums[i]=nums[j];
nums[j]=temp;
}
} //end for
for(int i=0;i<numsSize;i++)
{
if(nums[i]>0)
{
sum+=nums[i];
}
} //end for
return sum;
}
}
int main(){
int nums[]=[-2,1,-3,4,-1,2,1,-5,4];
int numsSize=9;
printf("%d",maxSubArray(nums,numsSize));
return 0;
}

正确的题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int maxSubArray(int* nums, int numsSize) {
int i,j;
if(numsSize<=0)
return 0;

int sum=0;
int realSum=nums[0];

for(i = 0;i<numsSize;i++){
sum+=nums[i];
// if sum is less than zero
if(sum<0){
realSum = (realSum>sum)?realSum:sum;
sum = 0;
continue;
}
// sum>0 判断当前数值和sum的大小,如果realSum 大则选择realSum 否则想下一个延伸
realSum = (realSum>sum)?realSum:sum;
}
return realSum;
}