最大子序和问题（C语言求解）

最大子序和问题（C语言求解）

题目描述如下：给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

这道题可用动态规划的方法求解，思路如下：

以序列【-2，1，-3，4】为例，该序列的长度为4，如果求解它的最大子序列的和呢？

假设我们已经知道，该序列中，所有长度为3的子序列的最大子序列的和，那么，你能否知道整个长度为4的序列的最大子序列的和？

我们来分情况讨论，有以下三种情况：

第一种是，最长的子序列发生了变化，也就是，最长的子序列长度为4，也就是【-2，1，-3，4】本身就是最长子序列，那么，子序列的和当然非常明确，就是这四个数相加 -2 + 1 + -3 + 4 = 0

第二种情况是，当考虑的序列长度为4时，最长子序列的长度没有发生变化，那么，最长的子序列长度依然藏在长度为3的最长子序列当中，即：要么是序列【-2，1，-3】的最长子序列，要么是序列【1，-3，4】的最长子序列。

我们只需要比较， 【-2，1，-3，4】本身； 序列【-2，1，-3】的最长子序列 ；序列【1，-3，4】的最长子序列，这三种情况，谁的值最大，谁就是最终答案即可。

那么，序列【-2，1，-3】的最长子序列 ，和序列【1，-3，4】的最长子序列，这两个值我又怎么知道呢？

可以用同样的思路分解：

以序列【-2，1，-3】为例，这是一个长度为3的序列，它的最长子序列，只有可能是以下三种情况：序列【-2，1，-3】本身，序列【-2，1】的最长子序列，序列【1，-3】的最长子序列。我们只需要从这三种情况中取出最大值即可。

那么，序列【-2，1】的最长子序列是谁呢？问题终于变得容易了：

要么为 -2，要么为1，要么为【-2，1】，显然，最大值为1。问题易解。

整个问题用公式来描述如下：

其中，i,j分别代表序列的下标，Mi,j代表序列从i到j的最大子序列，Sumi，j代表从i 到j元素的总和。

 这样，我们以可以建立一张二维表M，从序列长度为1开始填写，依次递增，直到将整张表填写完毕，假设序列长度为L，则即为最终值（这里假设下标从1开始）。

代码如下：

int getMaxSub(int * nums,int numsSize){
	int mx = nums[0];
	int m[100][100];
	int i;
	for(i=0;im[i][i+loopLen])
			    m[i][i+loopLen] = m[i+1][i+loopLen];
			if(m[i][i+loopLen-1]>m[i][i+loopLen])
			    m[i][i+loopLen] = m[i][i+loopLen-1];
			if(m[i][i+loopLen]>mx)
			    mx = m[i][i+loopLen];
		}
	}
	return mx;
}