blob: 3d66438dc1e9baeff196491c987ea8423d63fce3 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
def max_sum(arr, n):
MSIBS = arr[:]
for i in range(n):
for j in range(0, i):
if arr[i] > arr[j] and MSIBS[i] < MSIBS[j] + arr[i]:
MSIBS[i] = MSIBS[j] + arr[i]
MSDBS = arr[:]
for i in range(1, n + 1):
for j in range(1, i):
if arr[-i] > arr[-j] and MSDBS[-i] < MSDBS[-j] + arr[-i]:
MSDBS[-i] = MSDBS[-j] + arr[-i]
max_sum = float("-Inf")
for i, j, k in zip(MSIBS, MSDBS, arr):
max_sum = max(max_sum, i + j - k)
return max_sum
|
