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.
↵
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.
