I got an online test problem where they gave a string of characters and a value for each character. Value of each character is in range [-10, 10]. The problem was to find a substring that starts and ends with same character and has maximum value. The problem easily reduces to a extended version of maximum subarray sum problem after replacing the characters with values. The constraint is the starting and ending values will be same. I came up with a naive solution and was not good enough. Can anyone tell me how to work this out with Kadane's algorithm or any other with a better time complexity?
This question is designed to make Kadane's algorithm a bad fit.
You can still do it quickly and easily, though:
Iterate through the sequence, keeping track of the cumulative sum of values preceding each letter.
For each letter, remember the smallest preceding sum seen so far
At each letter, the maximum value sequence that ends there starts at the instance of the same letter with the smallest preceding sum seen so far. Note that that might be same position for a sequence with length 1.
It's easy to calculate the value of that best sequence ending at each letter: letter_value + preceding_sum - smallest_preceding_sum_for_same_letter. Remember the most valuable sequence you find.