给定一个数组,其所有元素都是正数,找到子序列的最大和,其中序列中没有2个数字应该在数组中相邻.所以3 2 7 10应该返回13(3和10的总和)或3 2 5 10 7应该返回15(3和5和7的总和).
我尝试使用所有可能的金额,然后找到最大值(强力方法),但有什么更好的方法.例如[3 2 7 10]我总和3,7和2,10并且最大.
更多例子
> [3,2,7,1]：返回10
> [6,1,4]：返回10
> [8,9,5,1]：返回13
> [29,77,16]：返回77
> [29,44,16]：返回45
解决方法
这个问题可以通过动态编程来解决.
假设我们有一个整数数组：
i[1],i[2],i[3],...,i[n],i[n+1],i[n+2]
我们将数组分成两部分：第一部分包含前n个整数,第二部分是最后两个整数：
{i[1],i[n]},{i[n+1],i[n+2]}
我们将M_SUM(n)表示为每个要求的前n个整数的最大和.
会有两种情况：
>如果i [n]不被计入M_SUM(n),则M_SUM(n 2)= M_SUM(n)MAX(i [n 1],i [n 2])
>如果i [n]被计入M_SUM(n),则M_SUM(n 2)= M_SUM(n)i [n 2]
那么M_SUM(n 2)我们正在寻找的值将是上述两者的较大值.
那么我们可以有一个非常幼稚的伪代码如下：
function M_SUM(n)
return MAX(M_SUM(n,true),M_SUM(n,false))
function M_SUM(n,flag)
if n == 0 then return 0
else if n == 1
return flag ? i[0] : 0
} else {
if flag then
return MAX(
M_SUM(n-2,true) + i[n-1],M_SUM(n-2,false) + MAX(i[n-1],i[n-2]))
else
return MAX(M_SUM(n-2,false) + i[n-2],true))
}
“flag”表示“允许使用最后一个整数”
该算法具有指数时间复杂度.
可以采用动态编程技术来消除M_SUM的不必要的重新计算.
将每个M_SUM(n,标志)存储到n * 2矩阵中.在递归部分,如果这样的值不存在于矩阵中,则计算它.否则,只需从矩阵中获取值.这将使时间复杂度降至线性.
该算法将具有O(n)时间复杂度和O(n)空间复杂度.
