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.

 

1 public class Solution { 2     public int MaxSubArray(int[] nums) { 3         int curSum = 0, result = Int32.MinValue; 4          5         int j = 0; 6         while (j < nums.Length) 7         { 8             curSum += nums[j]; 9             result = Math.Max(result, curSum);10             if (curSum < 0)11             {12                 curSum = 0;13             }14             15             j++;16         }17         18         return result;19     }20 }