How Far Have You Gotten in Leet

*** This solution came from kamal08111998’s article

Description

resource: link

Explanation

Given that an array would be modified by repeating it k times, the maximum sub-array sum depends on k.

1. If k is equal to 1, the maximum sum would be inside the array.
2. If more than 1, the sub-array having the maximum value might go beyond the range. So, we need to find it in the two-times repeated array.
3. If k is more than 2 and the maximum value comes from the sub-array connecting the first to the last section, it would mean that the value is to sum its normal sum k-2 times and add it to the one in the second value. If the former is a negative value, the latter should be the maximum itself.

Figure out that k and the normal sum is crucial to resolve this. In other words, in the first step, we need to use Kadane’s algorithm for the unmodified array. In the later steps, the algorithm would be applied to the array that repeats two times. In this situation, the normal sum is greater than zero, the sub-array should be long enough to cover that part so that the maximum sum would be to add the normal sum k-2 times and sum it with the Kadane sum.

***Please read this article to take a close look at the kadane’s algorithm.

Solution

Review

Caught the basic concept of the problem but difficult to resolve it without a clear understanding of Kadane’s algorithm. Need to figure out the concept more clearly.