Sum of all subarray maximums

Revision en2, by tmpuser-001, 2015-12-02 14:32:26

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))

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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English tmpuser-001 2015-12-02 14:34:59 122
en2 English tmpuser-001 2015-12-02 14:32:26 4
en1 English tmpuser-001 2015-12-02 14:31:45 505 Initial revision (published)