Given an array of integers and k moves, where in each move, we can collect the value at either end, find the maximum possible sum obtainable of the collected values.
Try all possibilities of consideration, such that you pick
i elements from the left end and
k-i elements from the right end for
0 <= i <= k.
To emphasize on the above solution, let us consider all possibilities:
i). no elements from the left end and k elements from the right end.
ii). one element from the left end and k-1 elements from the right end.
… and so on.
For each possibility, calculate the sum of all the picked elements, and find the maximum sum obtained across all iterations of this process.
Now, note we do not have to recalculate the entire sums from the left and right ends for every iteration. We only need to calculate the sum of the
k rightmost elements once. For every iteration, we add on an element from the left end to the sum, and remove an element from the right end from the sum.
Repeat this process
k times and find the maximum sum obtained in the process.
n = int(input()) l = list(map(int, input().split())) k = int(input()) leftSum = 0 leftPtr = 0 currSum = sum(l[n-k:]) rightPtr = n - k maxSum = currSum for i in range(k): currSum += l[leftPtr] leftPtr += 1 currSum -= l[rightPtr] rightPtr += 1 if currSum > maxSum: maxSum = currSum print(maxSum)
The time to read the input array is
The time to calculate maximum sum is
The overall time is