Problem:
 Score : 400 points    Problem Statement Your friend gave you a dequeue D as a birthday present.  D is a horizontal cylinder that contains a row of N jewels.  The values of the jewels are V_1, V_2, ..., V_N from left to right. There may be jewels with negative values.  In the beginning, you have no jewel in your hands.  You can perform at most K operations on D , chosen from the following, at most K times (possibly zero):    Operation A: Take out the leftmost jewel contained in D and have it in your hand. You cannot do this operation when D is empty.    Operation B: Take out the rightmost jewel contained in D and have it in your hand. You cannot do this operation when D is empty.    Operation C: Choose a jewel in your hands and insert it to the left end of D . You cannot do this operation when you have no jewel in your hand.    Operation D: Choose a jewel in your hands and insert it to the right end of D . You cannot do this operation when you have no jewel in your hand.    Find the maximum possible sum of the values of jewels in your hands after the operations.      Constraints  All values in input are integers.  1 \leq N \leq 50  1 \leq K \leq 100  -10^7 \leq V_i \leq 10^7         Input Input is given from Standard Input in the following format:  N  K  V_1  V_2  ...  V_N       Output Print the maximum possible sum of the values of jewels in your hands after the operations.        Sample Input 1 6 4
-10 8 2 1 2 6      Sample Output 1 14  After the following sequence of operations, you have two jewels of values 8 and 6 in your hands for a total of 14 , which is the maximum result.   Do operation A. You take out the jewel of value -10 from the left end of D .  Do operation B. You take out the jewel of value 6 from the right end of D .  Do operation A. You take out the jewel of value 8 from the left end of D .  Do operation D. You insert the jewel of value -10 to the right end of D .        Sample Input 2 6 4
-6 -100 50 -2 -5 -3      Sample Output 2 44       Sample Input 3 6 3
-6 -100 50 -2 -5 -3      Sample Output 3 0  It is optimal to do no operation.

Solution (Python):
N, K = map(int, input().split())
V = list(map(int, input().split()))
dp = [[-10 ** 10 for j in range(N+1)] for i in range(N+1)]

for i in range(N+1):
    for j in range(N+1):
        if i+j <= N and i+j <= K:
            nokori = K - i - j
            now = []
            now.extend(V[:i])
            if j != 0:
                now.extend(V[-j:])
            now.sort()
            nowmax = sum(now)
            
            
            for k in range(min(nokori, len(now))):
                nnn = now.pop(0)
                if nnn < 0:
                    nowmax -= nnn
                else:
                    break
            dp[i][j] = nowmax

ans = -10 ** 10
for i in range(N+1):
    ans = max(ans, max(dp[i]))
print(ans)

Solution (Python):
N, K = map(int, input().split())
V = [int(v) for v in input().split()]

nk = min(N, K)  
ans = 0

for i in range(1, nk + 1):   
    for j in range(i + 1):   
        tmp = V[:j] + V[N-i+j:] 
        tmp.sort()
        ngcnt = 0   
        vsum = 0
        for t in tmp:
            if t < 0 and ngcnt < K-i:
                ngcnt += 1
                continue
            else:
                vsum += t
        ans = max(vsum, ans)

print(ans)

Solution (Python):
import heapq

N,K=map(int,input().split())
inl = list(map(int,input().split()))

pq = []
max_score = 0

for i in range(min(N,K)+1):
    
    for j in range(min(N-i, K-i)+1):
        tmp_score = 0
        pq = []
        for lef in range(i):
            if inl[lef] < 0:
                heapq.heappush(pq, inl[lef])
            tmp_score += inl[lef]
        for rg in range(j):
            if inl[N-1-rg] < 0:
                heapq.heappush(pq, inl[N-1-rg])
            tmp_score += inl[N-1-rg]
        for _ in range(K-i-j):
            if len(pq):
                minus = heapq.heappop(pq)
                tmp_score -= minus
        
        
        max_score = max(tmp_score, max_score)

print(max_score)

Solution (Python):
list=input().split(" ")
n=int(list[0])
k=int(list[1])

list=input().split(" ")
for l in range(len(list)):
    list[l]=int(list[l])


maxpoint=0

for i in range(k+1):
    for j in range(i+1):
        if i>len(list):
            juery=list
        elif j==0:
            if j-i==0:
                juery=[]
            else:
                juery=list[j-i:]
        else:
            if j-i==0:
                juery=list[:j]
            else:
                juery=list[:j]+list[j-i:]
        juery=sorted(juery)
        
        point=0
        magic=min(k-len(juery), len(juery))
        for x in range(magic):
            if juery[x]<0:
                point-=juery[x]
        point+=sum(juery)
        
        if point>maxpoint:
            maxpoint=point

print(maxpoint)

Solution (Python):
import bisect


def f(a: list, n: int) -> list:
    i = bisect.bisect(a, 0)
    return a[min(i, n):]


assert f([1, 2, 3], 1) == [1, 2, 3]
assert f([-1, 2, 3], 1) == [2, 3]
assert f([-2, -1, 3], 1) == [-1, 3]
assert f([-2, 0, 3], 1) == [0, 3]
assert f([-2, -1, 3], 3) == [3]
assert f([-2, -1, 3], 0) == [-2, -1, 3]
assert f([], 0) == []


def main():
    
    N, K = map(int, input().split())
    V = [int(x) for x in input().split()]
    Vr = list(reversed(V))

    ans = -float("inf")
    for l in range(0, max(N, K)+1):
        for r in range(0, max(N, K)+1):
            n = max(0, K - r - l)  

            if N < l + r or K < l + r:
                continue

            
            a1 = V[:l]
            a2 = Vr[:r]
            a = a1 + a2
            a = sorted(a)

            score = sum(f(a, n))
            ans = max(ans, score)

            
            
            

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
n,k=map(int,input().split())
ls,lm,rs,rm=[0],[[0 for i in range(k+1)]for i in range(n+1)],[0],[[0 for i in range(k+1)]for i in range(n+1)]
v=list(map(int,input().split()))
ld=[]
rd=[]
for i in range(n):
    ls.append(ls[-1]+v[i])
    if v[i]<0:
        ld.append(v[i])
        ld=sorted(ld)
    for j in range(1,k+1):
        if j-1<len(ld):
            lm[i+1][j]=lm[i+1][j-1]+ld[j-1]
        else:
            lm[i+1][j]=lm[i+1][j-1]
    ii=n-i-1
    rs.append(rs[-1]+v[ii])
    if v[ii]<0:
        rd.append(v[ii])
        rd=sorted(rd)
    for j in range(1,k+1):
        if j-1<len(rd):
            rm[i+1][j]=rm[i+1][j-1]+rd[j-1]
        else:
            rm[i+1][j]=rm[i+1][j-1]


mx=-999999999
for w in range(k+1):
    for x in range(w+1):
        for y in range(x,w+1):
            for z in range(y,w+1):
                    a,b,c,d=x,y-x,z-y,w-z
                    if a+c<=n and len(ls)>a>=b and len(rs)>c>=d and ls[a]-lm[a][b]+rs[c]-rm[c][d]>mx:
                        
                        mx=ls[a]-lm[a][b]+rs[c]-rm[c][d]
print(mx)

Solution (Python):
from functools import lru_cache
import numpy as np

N,K=[int(i) for i in input().split(" ")]
V=[int(i) for i in input().split(" ")]

retval=0
for left in range(max(N+1,K+1)):
    for right in range(min(N-left+1,K-left+1)):
        modoseru=K-(left+right)
        temoto=np.asarray(sorted(V[:left:]+V[N-right::]))
        modosu=min(np.sum(temoto<0),modoseru)
        retval=max(sum(temoto[modosu::]),retval)

print(retval)

Solution (Python):
n, k = (int(v) for v in input().split())
vals = [int(v) for v in input().split()]

max_val = 0
for disc in range(max(k - len(vals), 0), k):
    pick = k - disc
    for lp in range(pick+1):
        if pick > lp:
            jewel = vals[:lp] + vals[-(pick-lp):]
        else:
            jewel = vals[:lp]
        neg = sum([j < 0 for j in jewel])
        if neg <= disc:
            reward = sum([j for j in jewel if j > 0])
        else:
            reward = sum(sorted(jewel)[disc:])
        if reward > max_val:
            max_val = reward
print(max_val)

Solution (Python):
import sys

fin = sys.stdin.readline

n, k = map(int, fin().split())
v = list(map(int, fin().split()))


if all([v_ <= 0 for v_ in v]):
    print(0)
else:
    scores = [0]
    for i in range(1, min(k, n) + 1):  
        for j in range(i + 1):
            poped = v[:j] + v[n - i + j:]
            poped = sorted(poped)
            if k ==i:
                scores.append(sum(poped))
            elif k >= i*2:
                scores.append(sum([max(0, p) for p in poped]))
            elif poped[k - i - 1] < 0:
                scores.append(sum(poped[k - i:]))
            else:
                scores.append(sum([max(0, p) for p in poped]))


    print(max(scores))

Solution (Python):
import sys
input=sys.stdin.readline
from collections import deque
from heapq import heappush,heappop
import re

def int_raw():
    return int(input())
 
def ss_raw():
    return input().split()
 
def ints_raw():
    return tuple(map(int, ss_raw()))


def main():
    N ,K = ints_raw()
    Vs = ints_raw()
    N = len(Vs)
    leftSum = [0]
    leftNegas = [[]]
    for v in Vs:
        leftSum.append(leftSum[-1]+v)
        neoNega = leftNegas[-1]
        if v<0:
            neoNega = neoNega+[v]
            neoNega.sort()
        leftNegas.append(neoNega )


    rightSum = [0]
    rightNegas = [[]]
    for v in Vs[::-1]:
        rightSum.append(rightSum[-1]+v)
        neoNega = rightNegas[-1]
        if v<0:
            neoNega = rightNegas[-1]+[v]
            neoNega.sort()
        rightNegas.append(neoNega )

    ans = 0
    for left_k in range(K+1):
        left_total = 0
        left_n = 0
        for n in range(min(N+1,left_k+1)):
            tmp = leftSum[n] - (sum(leftNegas[n]) if len(leftNegas[n])<=left_k-n else sum(leftNegas[n][:left_k-n]))
            if left_total < tmp:
                left_total = tmp
                left_n = n
        right_total = 0
        right_n = 0
        right_k = K -left_k
        for n in range(min(K-left_k+1,N-left_n+1)):
            tmp = rightSum[n] - (sum(rightNegas[n]) if len(rightNegas[n])<=right_k-n else sum(rightNegas[n][:right_k-n]))
            if right_total < tmp:
                right_total = tmp
                right_n = n
        ans = max(ans,left_total+right_total)
    return ans

print(main())

Solution (Python):
def run(N, K, V):
    ret = 0
    for L_get in range(K+1):
        for R_get in range(K-L_get+1):
            if L_get + R_get > N:
                break
            for Leave in range(K-L_get-R_get+1):
                if Leave > L_get + R_get:
                    break
                if L_get == 0:
                    L_lists = []
                else:
                    L_lists = V[:L_get]
                if R_get == 0:
                    R_lists = []
                else:
                    R_lists = V[-R_get:]
                lists = L_lists + R_lists
                sorted_lists = sorted(lists)
                ret = max(ret, sum(lists) - sum(sorted_lists[:Leave]))
    return ret


def main():
    N, K = map(int, input().split())
    V = list(map(int, input().split()))
    print(run(N, K, V))


if __name__ == '__main__':
    main()

Solution (Python):
N,K = list(map(int, input().split()))
V = list(map(int, input().split()))


from itertools import accumulate
Lcumsum = [0] + list(accumulate(V))
Rcumsum = [0] + list(accumulate(V[::-1]))



ans = 0
               
for l in range(min(N,K)+1):
  for r in range(min(N-l,K-l)+1):
    Lsum = Lcumsum[l]
    Rsum = Rcumsum[r]
    Nsum = sum(sorted([v for v in (V[:l] + V[N-r:]) if v<0])[:K-l-r])
    ans = max(ans, Lsum+Rsum-Nsum)
    
    
print(ans)

Solution (Python):
N, K = map(int, input().split(" "))
V = list(map(int, input().split(" ")))

max_score = 0
for i in range(N+1):
    
    for j in range(i, N+1):
        
        p = V[:i] + V[j:] 
        
        if len(p) > K:
            continue
        p.sort(reverse=True)
        for _ in range(K-len(p)):
            if p and p[-1]<0:
                p.pop()
            else:
                break
        score = sum(p)
        
        max_score = max(max_score, score)

print(max_score)

Solution (Python):

import sys
from collections import deque

def solve(N: int, K: int, V: "List[int]"):

    mani = []
    for ac in range(K+1):
        for bc in range(K+1):
            for cc in range(K+1):
                if (ac+bc+cc) == K:
                    mani.append([ac,bc,cc])

    max_v = 0
    for m in mani:
        VV = deque(V)
        MV = []
        lenVV = len(VV)
        for i in range(min(m[0],lenVV)):
            MV.append(VV.popleft())

        lenVV = len(VV)
        for i in range(min(m[1],lenVV)):
            MV.append(VV.pop())

        MV.sort()
        MV = deque(MV)
        for i in range(m[2]):
            if len(MV) > 0 and MV[0] < 0:
                MV.popleft()

        max_v = max(max_v,sum(MV))

    print(max_v)



            




def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    K = int(next(tokens))  
    V = [ int(next(tokens)) for _ in range(N) ]  
    solve(N, K, V)

if __name__ == '__main__':
    main()

Solution (Python):
n, k = list(map(int, input().split()))
v = list(map(int, input().split()))

total_all = []
for a in range(min(n, k) + 1):
    for b in range(min(k - a, n - a) + 1):
        if b == 0:
            tmp = v[:a]
        else:
            tmp = v[:a] + v[-1 * b:]
        tmp.sort()

        n_tmp_negative = sum(1 for x in tmp if x < 0)
        cd = k - a - b
        if cd > 0:
            total = sum(tmp[min(cd, n_tmp_negative):])
        else:
            total = sum(tmp)

        total_all.append(total)
print(max(total_all))

Solution (Python):
N, K = map(int, input().split())
V = [int(x) for x in input().split()]
L = [[] for i in range(K + 1)]
R = [[] for i in range(K + 1)]
for i in range(1, K + 1):
  L[i] = sorted(V[:i])
  R[i] = sorted(V[-i:], reverse=True)
ans = 0
for l in range(min(N, K) + 1):
  for r in range(min(N, K) + 1 - l):
    LR = L[l] + R[r]
    k = K - l - r
    while k > 0:
      if len(LR) and LR[0] <= LR[-1] and LR[0] < 0:
        LR.pop(0)
      elif len(LR) and LR[-1] <= LR[0] and LR[-1] < 0:
        LR.pop(len(LR) - 1)
      k -= 1
    ans = max(sum(LR), ans)
print(ans)

Solution (Python):
import bisect

N,K = map(int,input().split())
V = list(map(int,input().split()))

ans = 0

if N < K :
    pp = K
    K = N
else :
    pp = K
for a in range(1,K+1) :
    for i in range(a+1) :
        G = []
        G.extend(V[:i])
        G.extend(V[len(V)-(a-i):])
        G.append(0)
        G = sorted(G)
        
        

        cnt = 0
        calc = 0
        for i in range(len(G)) :
            if G[i] < 0 :
                if cnt < pp-a :
                    cnt += 1
                else :
                    calc += G[i]
            else :
                calc += G[i]


        ans = max(ans,calc)

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
import numpy as np





def solve():
    n, k = map(int, input().split())
    v_list = list(map(int, input().split()))

    temoti_max = 0
    for i in range(k+1):
        for j in range(min(k+1-i, n-i+1)):
            
            temoti_list = []
            temoti_list +=  v_list[:i]
            
            
            temoti_list += v_list[n-j:]
            
            temoti_list.sort()
            

            temoti = sum(temoti_list)
            for iret in range(min(len(temoti_list), k-i-j)):
                if temoti_list[iret] < 0:
                    temoti -= temoti_list[iret]

            if temoti_max <= temoti:
                temoti_max = temoti

    print(temoti_max)

solve()

Solution (Python):
n, k = map(int, input().split())
v = list(map(int, input().split()))
ans = 0
for l in range(n + 1):
	for r in range(l, max(n, l + 1)):
		o = v[:l] + v[r + 1:]
		if len(o) > k:
			continue
		o.sort()
		i = 0
		while i < len(o) and i < k - len(o) and o[i] < 0:
			i += 1
		ans = max(ans, sum(o[i:]))
		
print(ans)

Solution (Python):
n,k = map(int,input().split())


v = list(map(int,input().split()))
res = -(10**-12)

for left in range(min(n+1,k+1)):
    for right in range(min(n-left+1,k-left+1)):
        if right == 0:
            s = v[:left]
        else:
            s=v[:left]+v[-right:]
        s.sort()
        r = 0
        cnt = 0
        bound = k-left-right
        for i in s:
            if i<0 and cnt<bound:
                cnt+=1
            else:
                r+=i
        res = max(res,r) 
print(res)

Solution (Python):
n, k = map(int,input().split())

v = list(map(int, input().split()))

m = 0

for i in range(n + 1):

    for j in range(n, i - 1 , -1):

        temp = sorted(v[:i] + v[j:], reverse = True)

        count = len(temp)

        if count > k:
            break

        while temp and count < k and temp[-1] < 0:

            temp.pop()

            count += 1

        m = max(m, sum(temp))

print(m)

Solution (Python):
N, K = map(int, input().split(" "))
V = list(map(int, input().split(" ")))

ans = -1e+7
for n_get in range(1, min(N, K) + 1):
    n_remove = min(n_get, K-n_get)
    for n_front in range(n_get + 1):
        got = V[:n_front] + V[N-n_get+n_front:]
        got.sort()
        if n_remove > 0:
            if got[n_remove-1] < 0:
                got = got[n_remove:]
            else:
                got = [g for g in got if g > 0]
        ans = max(ans, sum(got))
print(ans)

Solution (Python):
N,K = map(int,input().split())
V = list(map(int,input().split()))
import heapq
ans = -float('inf')
for i in range(min(N+1,K+1)):
    for j in range(min(N-i+1,K-i+1)):
        A = V[:i]
        B = V[N-j:]
        AB = A + B
        heapq.heapify(AB)
        k = 1
        c = 0
        s = 0
        while i+j+k<=K and len(AB)>0:
            c = heapq.heappop(AB)
            if  c >= 0:
                break
            k += 1
        s = sum(AB)
        if c >= 0:
            s += c
        ans = max(ans,s)
print(ans)

Solution (Python):
import heapq
n,k=map(int,input().split())
V=[int(i) for i in input().split()]
M=sum(v for v in V if v>=0)
A=[[0,0]]
for i in range(1,n):
  VS=V[:i]
  cost=i
  A.append([cost,sum(VS)])
  heapq.heapify(VS)
  for _ in range(i):
    cost+=1
    heapq.heappop(VS)
    A.append([cost,sum(VS)])
B=[[0,0]]
V=V[::-1]
for i in range(1,n):
  VS=V[:i]
  cost=i
  B.append([cost,sum(VS)])
  heapq.heapify(VS)
  for _ in range(i):
    cost+=1
    heapq.heappop(VS)
    B.append([cost,sum(VS)])
ans=-float("inf")
for a in A:
  for b in B:
    if a[0]+b[0]<=k:
      ans=max(ans,a[1]+b[1])
print(M if n==1 else min(ans,M))

Solution (Python):
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

N,K = inpl()
vv = inpl()

ans = 0
for lnum in range(K+1):
    for rnum  in range(K-lnum+1):
        if lnum + rnum > N:
            continue
        torukazu = vv[:lnum] + vv[N-rnum:]
        torukazu.sort()
        
        for sute in range(K-lnum-rnum+1):
            
            tmp = sum(torukazu[sute:])
            ans = max(tmp,ans)

print(ans)

Solution (Python):
n,k=map(int,input().split())
v=list(map(int,input().split()))
ma=0
for i in range(k//2+1):
     pick=min(k-i,n)
     for j in range(pick+1):
          if j==0:
               l=v[:pick]
               al=l
          elif j==pick:
               r=v[-pick:]
               al=r
          else:
               l=v[:pick-j]
               r=v[-j:]
               al=l+r
          for rem in range(i):
               if len(al)>0:
                    mi=min(al)
                    if mi<0:
                         al.remove(mi)
                    else:
                         break
               else:
                    break
          if len(al)>0:
               ma=max(ma,sum(al))
print(ma)

Solution (Python):
n,k=map(int,input().split())
v_list=list(map(int,input().split()))
ans=0
for i in range(min(k+1,n+1)):
    for j in range(min(k-i+1,n-i+1)):
        List=v_list[:i]+v_list[n-j:]
        Sum=sum(List)
        List.sort()
        count=k-i-j
        x=0
        if List==[]:
            Sum=0
        else:
            while not count==0 and List[x]<0:
                Sum=Sum-List[x]
                count=count-1
                x=x+1
                if x==len(List):
                    break
        ans=max(ans,Sum)
print(ans)

Solution (Python):
N, K = map(int, input().split())
v = list(map(int, input().split()))
ans = 0
for i in range(min(N, K) + 1):
    for j in range(i + 1):
        h = v[:j] + (v[-(i - j):] if i != j else [])
        k = K - i
        tmp = sum(h)
        for m in range(i):
            h.sort()
            if k > 0 and h[m] < 0:
                k -= 1
                tmp -= h[m]
        ans = max(ans, tmp)
print(ans)

Solution (Python):
import bisect

n,k = (int(i) for i in input().split())
v = [int(i) for i in input().split()]

res = -10**10
for x in range( min(k+1,n+1) ):
    for l in range(x+1):
        r = x-l
        tras = k-x
        get = sorted(v[:l] + (v[-r:] if r!=0 else []))
        
        idx_0 = bisect.bisect_left(get,0)
        if res < sum(get[ min(idx_0,tras) :]):
            res = sum(get[ min(idx_0,tras) :])

print(res)

Solution (Python):
n,k = map(int, input().split())
v = list(map(int, input().split()))

ans = 0
for i in range(n+1):
    for j in range(i,n+1):
        a = v[:i]+v[j:]
        if len(a)>k:
            continue
        else:
            a.sort()
            a.reverse()
            for l in range(k-len(a)):
                if len(a)>0 and a[-1]<0:
                    a.pop()
                else:
                    break
            ans = max(ans, sum(a))
print(ans)

Solution (Python):
n,k = [int(i) for i in input().split()]
d = [int(i) for i in input().split()]
ans = 0
for en in range((k//2)+1):
    if en > n:
        break
    if k-en > n:
        tmp = d[:]
        tmp.sort()
        ans = max(ans, sum(tmp[en:]))
        continue
    for dl in range(k-en+1):
        tmp = d[:dl]+d[n-(k-en-dl):]
        tmp.sort()
        for j in range(en+1):
            ans = max(ans, sum(tmp[j:]))
print(ans)

Solution (Python):


def readInts():
  return [int(s) for s in input().split(" ")]

def max_val(V, n):
  count = n
  ret = 0
  for v in sorted(V):
    if v < 0 and count > 0:
      count -= 1
    else:
      ret += v
  return ret

def main():
  N, K = readInts()
  V = readInts()

  ans = 0

  for KL in range(K+1):
    KR = K - KL
    for L in range(min(KL, N)+1):
      for R in range(min(KR, N-L)+1):
        left = V[:L]
        right = V[-1 * R:] if R > 0 else []
        s = max_val(left, KL - L) + max_val(right, KR - R)
        ans = max(ans, s)

  print(ans)

if __name__ == "__main__":
  main()

Solution (Python):


import sys
import math
import collections

N, K = map(int, sys.stdin.readline().rstrip().split(" "))
Vs = list(map(int, sys.stdin.readline().rstrip().split(" ")))
result = 0
for L in range(min(N + 1, K + 1)):
    for R in range(min(N + 1 - L, K + 1 - L)):
        gems = Vs[:L]
        if R > 0:
            gems += Vs[-R:]

        gems.sort()
        rest = K - L - R
        
        for _ in range(rest):
            if len(gems) > 0 and gems[0] < 0:
                gems.pop(0)
            else:
                break
        
        result = max(result, sum(gems))
print(result)
exit(0)

Solution (Python):
N, K = map(int, input().split())
D = list(map(int, input().split()))

dp = [[[False for ___ in range(N+1)] for __ in range(N+1)] for _ in range(K+1)]

dp[0][0][N] = True

for k in range(K):
    for i in range(N+1):
        for j in range(i, N+1):
            if j+1<=N and i-1>=0:
                dp[k+1][i][j] = dp[k][i][j+1] or dp[k][i-1][j]
            elif j+1<N:
                dp[k+1][i][j] = dp[k][i][j+1]
            elif i-1>=0:
                dp[k+1][i][j] = dp[k][i-1][j]
                

ans = 0
for k in range(K+1):
    for n in range(K-k+1):
        for i in range(N+1):
            for j in range(i, N+1):
                if not dp[k][i][j]:
                    continue
                on_hand = D[:i]+D[j:]
                m = len(on_hand)
                if m < n:
                    continue


                ans = max(ans, sum(sorted(on_hand,reverse=True)[:m-n]))
print(ans)

Solution (Python):
import sys


N,K=map(int,input().split())

v=list(map(int,input().split()))
ans=0

for i in range(1,min(K,N)+1):
    for j in range(i+1):
        x=[v[k] for k in range(j)]+[v[k] for k in range(N-i+j,N)]
        tmp=sum(x)
        x.sort()
        
        for k in range(min(i,K-i)):
            if x[k]<0: tmp-=x[k]

        if tmp>ans: ans=tmp

print(ans)

Solution (Python):
import bisect
N,K=map(int,input().split())
V=list(map(int,input().split()))

sV=sorted(V)
ans=0
for i in range(N):
  for j in range(N-i+1):
    if i+j<=K:
      if i+j>=N:
        L=sV
      else:
        L=V[:i]+V[N-j:]
        L.sort()
      k=bisect.bisect_left(L,0)
      kans=sum(L[min(max(0,K-i-j),k):])
      ans=max(ans,kans)
print(ans)

Solution (Python):






def solve(V, K):
    hiscore = 0
    for k in range(0, K+1):
        lscore = sum(V[:k])
        rV = list(reversed(V[k:]))
        neg = [v for v in V[:k] if v < 0]
        for rk in range(0, K+1-k):
            neg0 = list(neg)
            rscore = lscore + sum(rV[:rk])
            neg0.extend(v for v in rV[:rk] if v < 0)
            score = rscore - sum(sorted(neg0)[:K-k-rk])
            if score > hiscore:
                
                hiscore = score
    print(hiscore)


N, K = [int(x) for x in input().split()]
V = [int(x) for x in input().split()]
solve(V, K)

Solution (Python):
N, K = map(int, input().split(' '))
V = list(map(int, input().split(' ')))


maxScore = 0
for p in range(K+1):
    
    for l in range(K+1-p):
        if l > N:
            continue
        for r in range(K+1-p-l):
            if l + r > N:
                continue
            d = K  - p - l - r
            if d < 0:
                continue
            if d > l + r:
                continue
            Vs = V[0:l]
            Vs += V[-r:] if r > 0 else []
            Vs.sort()
            score = sum(Vs[d:])
            maxScore = max(score, maxScore)
print(maxScore)

Solution (Python):
N, K = list(map(int, input().split()))
V = list(map(int, input().split()))

Ans = 0
M = min(N + 1, K + 1)
for i in range(M):
  S = V[:i]
  for j in range(M - i):
    if j == 0:
      P = S
    else:
      P = S + V[-j:]
    t = 0
    T = []
    for k in P:
      t += k
      if k < 0:
        T.append(k)
    T.sort()
    for k in range(min(len(T), K - (i + j))):
      t -= T[k]
    Ans = max(Ans, t)

print(Ans)

Solution (Python):
from itertools import product

N, K = map(int, input().split())
V = [int(x) for x in input().split()]

ans = 0

for l, r in product(range(K + 1), repeat=2):
    if l + r == 0 or l + r > N or l + r > K:
        continue

    A = V[:l] + V[N - r:]
    s = sum(A)

    
    a = K - (l + r)
    if a > 0:
        A = sorted(A)
        for i in range(min(a, len(A))):
            if A[i] < 0:
                s -= A[i]
            else:
                break
    ans = max(ans, s)
print(ans)

Solution (Python):
N,K = list(map(int,input().split()))

V = list(map(int,input().split()))



left_dict = {0:0}

for i in range(K,0,-1):
    left_dict[i]=max([sum(sorted(V[:i-j])[j:]) for j in range(i//2+1)])

left_dict



V = list(reversed(V))

V

right_dict = {0:0}
for i in range(K,0,-1):
    right_dict[i]=max([sum(sorted(V[:i-j])[j:]) for j in range(i//2+1)])

right_dict

m = 0
for i in range(K+1):
    for j in range(K-i+1):
        if m < left_dict[i]+right_dict[j]:
            m = left_dict[i]+right_dict[j]

            
print(min(m,sum([v for v in V if v>0 ]) ))

Solution (Python):

import itertools as it

N, K = map(int, input().split())
vs = [int(s) for s in input().split()]

acc = [0] + list(it.accumulate(vs))
res = 1000000000
for left in range(min(N, K) + 1):
    for right in range(min(N, K) + 1 - left):
        tmp = acc[N - right] - acc[left]
        rem = K - left - right
        rest = sorted(vs[:left] + vs[N - right :])[:rem]

        for x in rest:
            if x < 0:
                tmp += x
        if tmp < res:
            res = tmp

print(acc[-1] - res)

Solution (Python):
n, k = map(int, raw_input().split(" "))
v = map(int, raw_input().split(" "))

ans = 0
for k1 in range(0, min(n, k) + 1):
    for k2 in range(0, max(min(k - k1 + 1, n - k1 + 1), 0)):
        k3 = max(0, k - k1 - k2)

        gets = v[0:k1] + v[len(v)-k2:len(v)]
        sort = sorted(gets)

        sum = 0
        for i in range(0, len(sort)):
            if sort[i] < 0 and i <= k3 - 1:
                pass
            else:
                sum += sort[i]

        
            
            
        ans = max(sum, ans)

print(ans)

Solution (Python):
N, K = map(int, input().split())
V = list(map(int, input().split()))

ans = 0
for push_num in range(K // 2 + 1):
    gem_num = K - push_num
    
    if gem_num >= N:
        gem_list = list(V)
        gem_list.sort()
        for i_start, gemi in enumerate(gem_list):
            if i_start >= push_num: break
            if gemi > 0: break
        ans_tmp = sum(gem_list[i_start:])
        
        if ans < ans_tmp: ans = ans_tmp
        continue
    else:
        for l_num in range(gem_num + 1):
            r_num = gem_num - l_num
            gem_list = []
            for i in range(l_num): gem_list.append(V[i])
            for i in range(r_num): gem_list.append(V[-(r_num - i)])
            gem_list.sort()
            for i_start, gemi in enumerate(gem_list):
                if i_start >= push_num: break
                if gemi > 0: break
            ans_tmp = sum(gem_list[i_start:])
            
            if ans < ans_tmp: ans = ans_tmp

print(ans)

Solution (Python):

import sys
from math import ceil
from itertools import chain

def solve(N: int, K: int, V: "List[int]"):
    
    ans = -10**10
    for i in range(min(K+1, N+1)):
        max_n = min(K-i, i)
        for j in range(i+1):
            V2 = sorted(chain(V[:j], V[N-(i-j):]))
            k=0
            while True:
                if k>=max_n or V2[k]>=0:
                    break
                k+=1
            ans = max(sum(V2[k:]), ans)
    print(ans)

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    K = int(next(tokens))  
    V = [ int(next(tokens)) for _ in range(N) ]  
    solve(N, K, V)

if __name__ == '__main__':
    main()

Solution (Python):
N,K = map(int,input().split())
V = list(map(int,input().split()))
V_r = list(reversed(V))

ans = 0
for take in range(min(N+1,K+1)):
	for left in range(take+1):
		right = take - left
		jewel = V[:left] + V_r[:right]
		rest = K - take
		jewel.sort()
		tmp = sum(jewel)
		for i in range(min(take,rest)):
			if jewel[i] < 0:
				tmp -= jewel[i]
		ans = max(ans, tmp)
print(ans)

Solution (Python):
read = input 
rn = lambda :list(map(int, read().split()))

n, k = rn()
V = rn() 
best = 0
for i in range(0, n + 1): 
    for j in range(i, n+1): 
        
        yes = V[0:i] + V[j: n]
        if len(yes) > k:
            continue
        leftout = k - len(yes)
        yes.sort()
        skip = 0
        for skip in range(len(yes)):
            if yes[skip] <0 and leftout > 0:
                leftout -= 1
            else :
                break
        if best < sum(yes[skip:]):
            best = sum(yes[skip:])

print(best)