c++ - 根据给定标准的最大总和

Question

我正在解决作为作业给我的一个问题。我努力尝试但无法达到最佳解决方案。

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!

我想在保留 L(i) 的同时应用最大子数组和作为标准。这是代码->>

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];
    }

这对很多测试用例都不起作用!有更好的解决方案吗？

Answer 1

令 F[i] 等于最后一次访问的商店是 i 时可获得的最大幸福度。

您可以通过计算所有有效前驱(j < i 且 L[j] <= L[i])的最大值，根据先前值 F[j] 计算 F[i]。

那么你能做的最好的就是F[i]中的最大值。