如果只从前部或后部选取元素，则k数的最大值之和

Question

求整数数组k个数的最大和

只允许从前端或后端操作。

案例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

案例2

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

案例3

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

Answer 1

如果从前面取i元素，则需要从后面提取k-i元素并对它们进行求和。目标是找到这样一个最大和的0<=i<=k。

因此，朴素的O(K^2)解可以是：

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)

只要稍加修改，它就可以转化为O(K)。注意，一旦计算了i==0的和，我们只需要在当前的示例中添加100并减去200，就可以得到total for i==1。所以：

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]

运行时，如果从前面取出total元素，则打印和(即此处的i )：

0 202
1 102
2 101