# C#LeetCode刷题之#53-最大子序和（Maximum Subarray）

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Input: [-2,1,-3,4,-1,2,1,-5,4],

Output: 6

Explanation: [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.

```public class Program {

public static void Main(string[] args) {
int[] nums = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };

var res = maxSubArray(nums);
Console.WriteLine(res);

nums = new int[] { 4, 1, 0, -3, -1, 9, 1 };

res = maxSubArray2(nums);
Console.WriteLine(res);

}

private static int maxSubArray(int[] nums) {
//常规写法
//记录最大和、本次可以“接受”的和（本次和）
var max = int.MinValue;
var thisSum = 0;
for(var i = 0; i < nums.Length; i++) {
//如果和小于等于0，那么当前值没有用，应当舍去
//（为了优化写法，其实是上一次循环时的和）
//即重置本次和为当前值
if(thisSum <= 0) {
thisSum = nums[i];
} else {
//否则，迭加和
thisSum += nums[i];
}
//用max记录更大的值
if(max < thisSum) {
max = thisSum;
}
}
//返回最大值
return max;
}

private static int maxSubArray2(int[] nums) {
//高度精简优化写法
var max = int.MinValue;
var thisSum = 0;
for(var i = 0; i < nums.Length; i++) {
max = Math.Max(max, thisSum = Math.Max(nums[i], thisSum + nums[i]));
}
return max;
}

}```

```6
11```