-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathleetcode_53_maximum_subarray.c
More file actions
67 lines (56 loc) · 2.24 KB
/
leetcode_53_maximum_subarray.c
File metadata and controls
67 lines (56 loc) · 2.24 KB
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include "stdio.h"
#include "unistd.h"
#include "stdlib.h"
#include "string.h"
/*
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.
*/
int maxSubArray(int* nums, int numsSize) {
int i;
int maxSum = nums[0],curSum = nums[0];
int maxBegin = 0, maxEnd = 0;
int curBegin = 0;
for( i = 1; i < numsSize; i++ ) {
curSum += nums[i];
//drop the begin if it's negative.
if( nums[curBegin] <= 0 ) {
curSum -= nums[curBegin];
curBegin++;
}
//drop all nums before if sum is less than 0 and less than cur num
if( curSum <= nums[i] ) {
curSum = nums[i];
curBegin = i;
maxBegin = i;
}
//check maxSum
if( curSum > maxSum ) {
maxSum = curSum;
maxEnd = i;
}
}
printf( "%d-%d\n", nums[maxBegin], nums[maxEnd] );
return maxSum;
}
/*
his problem was discussed by Jon Bentley (Sep. 1984 Vol. 27 No. 9 Communications of the ACM P885)
the paragraph below was copied from his paper (with a little modifications)
algorithm that operates on arrays: it starts at the left end (element A[1]) and scans through to the right end (element A[n]), keeping track of the maximum sum subvector seen so far. The maximum is initially A[0]. Suppose we've solved the problem for A[1 .. i - 1]; how can we extend that to A[1 .. i]? The maximum
sum in the first I elements is either the maximum sum in the first i - 1 elements (which we'll call MaxSoFar), or it is that of a subvector that ends in position i (which we'll call MaxEndingHere).
MaxEndingHere is either A[i] plus the previous MaxEndingHere, or just A[i], whichever is larger.
public static int maxSubArray(int[] A) {
int maxSoFar=A[0], maxEndingHere=A[0];
for (int i=1;i<A.length;++i){
maxEndingHere= Math.max(maxEndingHere+A[i],A[i]);
maxSoFar=Math.max(maxSoFar, maxEndingHere);
}
return maxSoFar;
}
*/
int main( void ) {
int nums[] = {-2,1,-3,4,-1,2,1,-5,4};
int size = sizeof( nums ) / sizeof( int );
printf( "maxSum:%d\n", maxSubArray( nums, size ) );
}