问题：

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

思路：题意为给定 n 个整数(可能为负数)组成的序列 a[1],a[2],a[3],...,a[n],求该序列如
a[i]+a[i+1]+...+a[j]的子段和的最大值。当所给的整数均为负数时定义子段和为
0,如果序列中全部是负数则最大子断和为0,依此定义,所求的最优值为 Max{0,a[i]+a[i+1]+...+a[j]},1≤i≤j≤n。
例如 输入:-2,11,-4,13,-5,-2
输出:20

则此题可通过动态规划求解

首先计算辅助数组。
接着计算辅助数组的最大值。

辅助数组b[j]用来记录一j为尾的子段和集合中的最大子断和。

例如，假如有一序列：-2，11，-4，13，-5，-2
则
          b(1) = -2 ,b(2) = 11, b(3) = 7, b(4) = 20, b(5) = 15, b(6) = 13
          a(1) = -2, a(2) = 11, a(3) = 7, a(4) = 13, a(5) =  -5, a(6) = -2
          b(1) < 0    b(2) > 0    b(3) > 0  b(4) > 0   b(5) > 0     b(6) > 0
---->
                        { b(j - 1) + a(j)                     当b(j-1) >= 0
              b(j) = {
                        {a(j)                                      当b(j-1) < 0

代码：

public class Solution {

    public int MaxSubArray(int[] nums) {

        int sum = ;

        int[] dp = new int[nums.Length];

        int temp = ;

        for(int i = ; i < nums.Length; i++)

        {

            if(temp > )

                temp += nums[i];

            else

                temp = nums[i];

            dp[i] = temp;

        }

        sum = dp[];

        for(int i = ; i < dp.Length; i++)

        {

            if(sum < dp[i])

                sum = dp[i];

        }

        return sum;

    }

}