非连续元素的最大总和 [英] Maximum sum of non consecutive elements

问题描述

由于正整数数组，什么是最有效的算法找出此数组不连续的元素，当加在一起，产生最大的一笔？

Given an array of positive integers, what's the most efficient algorithm to find non-consecutive elements from this array which, when added together, produce the maximum sum?

推荐答案

动态规划？给定一个数组 A [0到n] ，让 M（I）正在使用的元素的最优解指数 0..i 。然后 M（-1）= 0 （在复发使用）， M（0）= A [0] 和 M（I）= MAX（M（I - 1），M（1 - 2）+ A [1]），其中i = 1，...，N 。 M（N）是我们想要的解决方案。这是O（n）。您可以使用另一个阵列来存储的选择是由每个子问题，并因此恢复实际内容选择。

Dynamic programming? Given an array A[0..n], let M(i) be the optimal solution using the elements with indices 0..i. Then M(-1) = 0 (used in the recurrence), M(0) = A[0], and M(i) = max(M(i - 1), M(i - 2) + A[i]) for i = 1, ..., n. M(n) is the solution we want. This is O(n). You can use another array to store which choice is made for each subproblem, and so recover the actual elements chosen.

这篇关于非连续元素的最大总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！