题目
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
3Input: [-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
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 | int maxSubArray(int* nums, int numsSize) { |