CODEWITHSUNDEEP
dynamic-programming
Santanu Sahoo
Santanu Sahoo

Reputation: 1157

Maximum sum of k numbers if elements are picked only from front or rear end

Find maximum sum of k numbers of an integer array

allowed operation only from front end or rear end.

case 1

k = 2
{1,2,3,6}
possible move (1,2), (1,6),(6,3),(6,1)
max sum = 9// for move (1,2) after removal of 1 the only choice is 2 and 6

case 2

k = 2
{100,1,200,2} 
o/p = max sum = 202

case 3

k = 2
{100,1,200,2} 
o/p => max sum = 100

Upvotes: 1

Views: 909

Answers (1)

Shihab Shahriar Khan
Shihab Shahriar Khan

Reputation: 5455

If you take i elements from front, you need to take k-i elements from back and sum over them. Goal is to find such an 0<=i<=k that maximizes the sum.

So, naive O(K^2) solution can be:

arr = [100,1,200,2]
k = 2
n = len(arr)

total = 0
for i in range(k+1): #i can be 0..k inclusive
    for j in range(i): #take 'i' elements from front 
        total += arr[j]
    for j in range(k-i): #take 'k-i' elements from back
        total += arr[n-1-j]
    print(i,total)

with just a little modification, it can be turned O(K). Notice once sum for i==0 is computed, we just need to add 100 and subtract 200 in this current example to get total for i==1. So:

for i in range(k+1):
    if i>0:
        total += (arr[i-1] - arr[n-k-1+i])
        print(i,total)
        continue
    for j in range(i):
        total += arr[j]
    for j in range(k-i):
        total += arr[n-1-j]

when run, it prints the sum (i.e total here), if i elements are taken from front:

0 202
1 102
2 101

Upvotes: 1

Related Questions