### tmpuser-001's blog

By tmpuser-001, history, 6 years ago,

I want to compute sum of maximum of all sub arrays in O(n)

till now i came up with an O(n^2) algo.

for better explanation of the problem, I want to reduce the complexity of this one liner.

print sum(max(arr[i:j]) for i, j in combinations(xrange(len(arr)), 2))


also assume that the array may contain equal elements.

Sample Test:
Input:
5
1 2 1 1 2
Output:
16