这道题目和数组求最大子数组问题有点相似,具体请看最大子数组和。
题目读起来有些拗口,本题是这个意思:即以i为结尾的数组包括如下类型
依题意,以i为结尾的最大子数组必定是如下两种类型种的一种:
第一种:
第二种:
第一种类型,我们使用求最大子数组和的方法就可以解决。
对于第二种类型,我们知道,数组的总和是固定的,如果我们可以求出以i为结尾的最小数组和,那不就相当于得到了以i为结尾的最大子数组和了嘛。
即:
设:f[i]:以i为结尾的所有子数组的最大值,
g[i]:以i为结尾的所有子数组的最小值。
f[i]:
g[i]:
注意:假设有一组数组为:-1,-2,-3, fmax=-1;sum=-6;gmin=-6,如果按照我们所说的,比较fmax和sum-gmin,那么取其较大者为0,这种情况是不对的,遇到元素都是负数的情况,需要二外讨论。
初始化视为类解决越界问题,那么什么时候会出现越界的情况呢??
当i=0时,i-1=-1,会出现越界的情形,我们可以初始化f[0]=nums[0],g[o]=nums[0];
f[i],g[i]同时填表比较好,从左往右。
设f表中的最大值为fmax,g表中的最小值为gmin,数组元素总和为sum,比较fmax和sum-gmin,返回其较大者。