LeetCodeOnlineJudge题目C#练习-MaximumSubarray

OGeek|极客世界-中国程序员成长平台 › 门户 › 编程› Node.js›Node.js教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

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.

 1         public static int MaximumSubarray(int[] A)
 2         {
 3             int n = A.Length;
 4             int max = A[0], max_neg = A[0], sum = 0;
 5             bool flag = false; // for all the elements are negative integers
 6             for (int i = 0; i < n; i++)
 7             {
 8                 //if found one is not negative, toggle flag. And keep tracking the max negative number
 9                 if (A[i] >= 0)
10                     flag = true;
11                 else if (A[i] > max_neg)
12                     max_neg = A[i];
13 
14                 sum += A[i];
15                 if (sum < 0)
16                     sum = 0;
17                 else if (sum > max)
18                     max = sum;
19             }
20 
21             return flag ? max : max_neg;
22         }