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.
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 |
class
Solution {public: int
maxSubArray(int
A[], int
n) { vector<int> sum; if(n == 0)return
0; int
maxsum =A[0]; sum.push_back(A[0]); for(int
i = 1 ; i < n ; i++) { int
temp = sum[i-1]+A[i]; if(temp > maxsum)maxsum = temp; sum.push_back(temp); } int
min = 0; for(int
i = 1 ; i < n;i++) { if(sum[i] - sum[min] > maxsum) maxsum = sum[i] - sum[min]; if(sum[i] < sum[min])min = i; } return
maxsum; }}; |
Maximum Subarray,布布扣,bubuko.com
原文：http://www.cnblogs.com/pengyu2003/p/3595264.html