JUN2- Editorial

PROBLEM LINK:

Practice
Contest

Author: Hemanth Kumar
Tester: Hrushikesh Koyadala
Editorialist: Hemanth Kumar

DIFFICULTY:

EASY

PREREQUISITES:

Two Pointers

PROBLEM:

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.

QUICK EXPLANATION:

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.

EXPLANATION:

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.

SOLUTIONS:

Setter's Solution
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)

TIME COMPLEXITY:

The time to read the input array is O(N).
The time to calculate maximum sum is O(K).
The overall time is O(N).