### LeetCode: 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.

Example:

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.

current: 存放目前元素的子陣列和
result: 存放已計算過後的最大子陣列和

current與result一開始皆設於nums[0]

using System;

namespace Maximum_Subarray_Easy
{
class Program
{
static void Main(string[] args)
{
int[] nums = new int[] { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
int result = maxSubArray(nums);
Console.WriteLine(result);
}

public static int maxSubArray(int[] nums)
{
int result = nums[0];
int current = nums[0];

for (int i = 1; i < nums.Length; i++)
{
current += nums[i];

if (current < 0 || current < nums[i])
current = nums[i];

if (current > result)
result = current;
}

return result;
}

}
}