最大子序和问题(C语言求解)

最大子序和问题(C语言求解),第1张

大子序和问题(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;
}

 

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/4653735.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-11-06
下一篇 2022-11-06

发表评论

登录后才能评论

评论列表(0条)

保存