CODEWITHSUNDEEP
c++algorithmdynamic-programming
user2826871
user2826871

Reputation: 29

maximum sum according to given criteria

I was solving one question given me as an assignment. I tried hard but unable to reach optimal solution.

There are N shops, all aligned linearly having index 1,2,3...N. Buying any positive number of items from a shop S(i) gives a happiness equal to H(i) . Unfortunately due to some unavoidable circumstances, every shop owner has introduced a value L(i). You are credited H(i) happiness from the ith shop if and only if this is the first shop you are buying something from or you buy at least one item from this shop and the last shop you shopped from was S(j) such that L(j)≤L(i) and j<i. Find the maximum sum of happiness that can be obtained following the rules given above!

I thought to apply max subarray sum along with keeping L(i) as criteria. here is the code->>

long long ans=INT_MIN, temp=0, prev=-1;

for(int i=0;i<n;i++){
    l = L[i];
    if(l>=prev){
        temp+=H[i];
        if(temp<0){
            temp = 0;
            prev = -1;
        }
        if(temp>ans){
            ans = temp;
            prev=L[i];
        }
    }
    else{
        if(H[i]>ans){
            ans = H[i];
            prev = L[i];
            temp = H[i];
        }
        else if(H[i] == ans && L[i]<prev)
            prev = L[i];
    }

This doesn't work on many test cases! Any better solution?

Upvotes: 1

Views: 134

Answers (2)

turoni
turoni

Reputation: 1435

L[i] will determine the possible paths you can take so I think you should be able to build multiple trees with different starting points from L[i] with each node containing H[i] as value. Then you do a traversal of this tree and the sum in each leave gives you the possible happiness.

Upvotes: 0

Peter de Rivaz
Peter de Rivaz

Reputation: 33499

Let F[i] be equal to the maximum happiness obtainable if the last shop visited is i.

You can compute F[i] from previous values F[j] by computing the maximum over all valid predecessors (those with j < i and L[j] <= L[i]).

Then the best you can do is the largest value in F[i].

Upvotes: 2

Related Questions