具有相同起始和结束元素的最大子数组和
Maximum subarray sum with same starting and end element
我遇到了一道在线测试题，他们给出了一串字符和每个字符的值。每个字符的值在 [-10, 10] 范围内。问题是找到一个以相同字符开头和结尾并具有最大值的子字符串。
用值替换字符后，该问题很容易简化为最大子数组和问题的扩展版本。约束是起始值和结束值将相同。我想出了一个天真的解决方案，但还不够好。
谁能告诉我如何使用 Kadane 的算法或任何其他具有更好时间复杂度的算法来解决这个问题？
此题旨在使 Kadane 的算法不合适。
不过，您仍然可以快速轻松地完成此操作：
遍历序列，跟踪每个字母前的值的累积和。
对于每个字母，记住目前看到的最小的前面总和
在每个字母处，以 结束的最大值序列开始于 在同一字母的实例处，其前面的总和最小。请注意，对于长度为 1 的序列，这可能是相同的位置。
计算以每个字母结尾的最佳序列的值很容易：letter_value + preceding_sum - smallest_preceding_sum_for_same_letter。记住你找到的最有价值的序列。
我遇到了一道在线测试题，他们给出了一串字符和每个字符的值。每个字符的值在 [-10, 10] 范围内。问题是找到一个以相同字符开头和结尾并具有最大值的子字符串。 用值替换字符后，该问题很容易简化为最大子数组和问题的扩展版本。约束是起始值和结束值将相同。我想出了一个天真的解决方案，但还不够好。 谁能告诉我如何使用 Kadane 的算法或任何其他具有更好时间复杂度的算法来解决这个问题？
此题旨在使 Kadane 的算法不合适。
不过，您仍然可以快速轻松地完成此操作：
遍历序列，跟踪每个字母前的值的累积和。
对于每个字母，记住目前看到的最小的前面总和
在每个字母处，以 结束的最大值序列开始于 在同一字母的实例处，其前面的总和最小。请注意，对于长度为 1 的序列，这可能是相同的位置。
计算以每个字母结尾的最佳序列的值很容易：letter_value + preceding_sum - smallest_preceding_sum_for_same_letter。记住你找到的最有价值的序列。