题目描述如下:给定一个整数数组 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; }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)