We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Data Structures
  3. Advanced
  4. Sum of the Maximums
  5. Discussions

Sum of the Maximums

  • vizzy205
     + 0 comments

    I feel like dp should be capable of helping. Just dont know how to implement. My code so far.

    from itertools import combinations
def solve(a, queries):
    n=len(a)
    dp=[]
    for i in range(n):
        dp+=[[0]*n]     
    #print(dp)
    
    for i in range(n):
        for j in range(n):
            if i==j:
                dp[i][j]=a[j]
            elif j>i:
                dp[i][j]=max(a[i:j+1])    
    #print(dp)
    
    l=[]
    for x,y in queries:
        count=0
        if x==y:
            print(dp[x-1][y-1])
        else:
            for i in range(x-1,y):
                for j in range(i,y):
                    #print(i,j)
                    count+=dp[i][j]
            print(count)
        
    #print(l)
    #return l