[数据结构与算法]动态规划问题 最大子序和

题目： 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。（LeetCode 53题）
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

官方的解释是这样的：假设nums 数组的长度是 n，下标从 0 到 n-1。

我们用 f(i) 代表以第 i 个数结尾的连续子数组的最大和，那么很显然我们要求的答案就是：

max{f(i)} 0<=i<=n-1

因此我们只需要求出每个位置的 f(i)，然后返回 f 数组中的最大值即可。那么我们如何求 f(i) 呢？我们可以考nums[i] 单独成为一段还是加入 f(i-1) 对应的那一段，这取决于 nums[i] 和 f(i-1) + nums[i]的大小，我们希望获得一个比较大的，于是可以写出这样的动态规划转移方程：

f(i) = max { f(i-1) + nums[i], nums[i] }

这个答案最开始让我迷惑的点就是以第 i 个数结尾的连续子数组的最大和，后来看到了一个答案让我明白了这句话。
我们在找子数组的时候第一个想到的总是以哪个元素开头的子数组比如[1,2,3]以1开头的子数组有[1] [1,2] [1,2,3]。但是上面说的让我迷惑的那句话是以某个数为结尾来找连续子数组比如以3为结尾的子数组有[3] [2,3] [1,2,3]。只要想通了从连续数组的结尾为基准那么上面那个动态规划转移方程就不难理解了。

根据方程，我们只需要遍历一遍数组就可以得到结果

public class Solution {
    public int MaxSubArray(int[] nums) {
       int max=nums[0];	//连续子数组最大和也就是方程中的f(i),用第一个元素初始化  
       int pre=nums[0];	//用来存储f(i-1)，最开始存的是f(0)
       for(int i=1;i<nums.Length;i++){
			pre=Math.Max(pre+nums[i],nums[i]);	//这一步取f(i)的值
			max=Math.Max(max,pre);	//选出最大的f(i)
		}
       return max;
    }
}