CODEWITHSUNDEEP
arraysalgorithmkadanes-algorithm
Kushal Mondal
Kushal Mondal

Reputation: 111

Maximum subarray sum with same starting and end element

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?

Upvotes: 0

Views: 588

Answers (1)

Matt Timmermans
Matt Timmermans

Reputation: 59174

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.

Upvotes: 1

Related Questions