c编程难题
给定一个数组,其所有元素都是正数,找到子序列的最大和,其中序列中没有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 解决方法
这个问题可以通过动态编程来解决.
假设我们有一个整数数组: 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]) 那么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)空间复杂度. (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |