algorithm - 可以给我们最大 'flip-flop' 总和的子列表数组是什么？

Question

我的问题是我得到了一个长度为 l 的数组。

假设这是我的数组:[1,5,4,2,9,3,6] 我们称它为 A。

这个数组可以有多个子数组，子数组的节点彼此相邻。所以我们可以有 [1,5,4] 或 [2,9,3,6] 等等。每个子数组的长度无关紧要。

但诀窍在于求和部分。我们不能只添加所有数字，它就像触发器一样工作。所以对于子列表 [2,9,3,6] 总和将是 [2,-9,3,-6] 即:-10 。而且很小。产生最大总和的数组 A 的子列表(或子数组，如果你愿意)是什么？一种可能的方法是(根据直觉)子列表 [4,2,9] 将输出一个不错的结果:[4, -2, 9] = (add所有元素)= 11。

问题是，如何得出这样的结果？给我们最大触发器和的子数组是什么？

主要是什么算法以任意数组为输入，输出一个所有数字相邻且总和最大的子数组？

我还没有想出任何办法，但我很确定我应该选择动态规划或分而治之来解决这个问题。再一次，我不知道，我可能完全错了。

Answer 1

这个问题确实可以使用动态规划来解决，方法是跟踪每个位置结束的最大总和。

但是，由于可以将当前元素添加到总和或从总和中减去(取决于子序列的长度)，我们将单独跟踪此处结束的最大总和，两者同样如此作为奇数子序列长度。

下面的代码(在 python 中实现)就是这样做的(请参阅代码中的注释以了解更多详细信息)。时间复杂度为O(n)。

a = [1, 5, 4, 2, 9, 3, 6]

# initialize the best sequences which end at element a[0]
# best sequence with odd length ending at the current position
best_ending_here_odd = a[0] # the sequence sum value
best_ending_here_odd_start_idx = 0
# best sequence with even length ending at the current position
best_ending_here_even = 0   # the sequence sum value
best_ending_here_even_start_idx = 1

best_sum = 0
best_start_idx = 0
best_end_idx = 0
for i in range(1, len(a)):
    # add/subtract the current element to the best sequences that
    # ended in the previous element
    best_ending_here_even, best_ending_here_odd = \
        best_ending_here_odd - a[i], best_ending_here_even + a[i]

    # swap starting positions (since a sequence which had odd length when it
    # was ending at the previous element has even length now, and vice-versa)
    best_ending_here_even_start_idx, best_ending_here_odd_start_idx = \
        best_ending_here_odd_start_idx, best_ending_here_even_start_idx

    # we can always make a sequence of even length with sum 0 (empty sequence)
    if best_ending_here_even < 0:
        best_ending_here_even = 0
        best_ending_here_even_start_idx = i + 1

    # update the best known sub-sequence if it is the case
    if best_ending_here_even > best_sum:
        best_sum = best_ending_here_even
        best_start_idx = best_ending_here_even_start_idx
        best_end_idx = i
    if best_ending_here_odd > best_sum:
        best_sum = best_ending_here_odd
        best_start_idx = best_ending_here_odd_start_idx
        best_end_idx = i

print(best_sum, best_start_idx, best_end_idx)

对于问题中的示例序列，上述代码输出以下触发器子序列:

4 - 2 + 9 - 3 + 6 = 14