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
please help me.
PS: sorry for this duplicate post, when i'm editing the problem statement, i clicked discard button thinking that it will discard the edits but it deleted the entire post.