arrays - 具有相同起始和结束元素的最大子数组和

Question

我遇到了一个在线测试问题，他们给出了一串字符和每个字符的值。每个字符的值在 [-10, 10] 范围内。问题是要找到一个以相同字符开头和结尾并且具有最大值的子字符串。在用值替换字符后，该问题很容易简化为最大子数组和问题的扩展版本。约束是起始值和结束值将相同。我想出了一个天真的解决方案，但还不够好。谁能告诉我如何使用 Kadane 的算法或任何其他具有更好时间复杂度的算法来解决这个问题？

Answer 1

这个问题旨在使 Kadane 的算法不适合。

不过，您仍然可以快速轻松地完成此操作：

• 遍历序列，跟踪每个字母之前的值的累积总和。

• 对于每个字母，记住迄今为止看到的最小的前面的总和

• 在每个字母处，到此结束的最大值序列开始于同一个字母的实例，其中前面的总和最小。请注意，对于长度为 1 的序列，这可能是相同的位置。

• 计算以每个字母结尾的最佳序列的值很容易：letter_value +preceding_sum - minimum_preceding_sum_for_same_letter。记住你找到的最有价值的序列。