Leetcode notes - dynamic planning -day7

LeetCode Brush notes - Dynamic programming -day7

1014. The best combination of sightseeing

1. subject

Original link ：1014. The best combination of sightseeing

2. Their thinking

1. Observe carefully a[i] + a[j] + i - j, Decomposable into ：(a[j]-j)+(a[i]+i)
2. Again because i<j, We can j As current point , So we only need to traverse this problem . Use a variable f maintain j All before the dot a[i]+i The maximum of
3. res=max(res,f+a[j]-j); The maximum value can be obtained by scanning once

3. Code

class Solution {
    
public:
    int maxScoreSightseeingPair(vector<int>& a) {
    
        int f=a[0];
        int res=-1e9;
        for(int i=1;i<a.size();i++){
    
            res=max(res,f+a[i]-i);
            f=max(a[i]+i,f);
        }
        return res;
    }
};

121. The best time to buy and sell stocks

1. subject

Original link ：121. The best time to buy and sell stocks

2. Their thinking

1. Use a variable minn maintain [0,i-1] The minimum price of
2. Enumerate to i when ,prices[i]-minn It means the current point i The biggest gain from selling
3. Traverse all points , Taking the maximum ：res=max(res,prices[i]-minn);

3. Code

class Solution {
    
public:
    int maxProfit(vector<int>& prices) {
    
        int minn=1e9,res=0;
        for(int i=0;i<prices.size();i++){
    
            res=max(res,prices[i]-minn);
            minn=min(minn,prices[i]);
        }
        return res;
    }
};

122. The best time to buy and sell stocks II

1. subject

Original link ：122. The best time to buy and sell stocks II

2. Their thinking

Algorithm ： greedy

The specific situation can be divided into three categories ：

1. Single trading day ： Set today's price P1、 Tomorrow's price P2, Then buy today 、 Exempt the earned amount tomorrow P2−P1( Negative values represent losses )
2. Continuous rising trading day ： Let the stock prices on this rising trading day be P1,P2,…,Pn Buy on the first day and sell on the last day , namely Pn−P1; Equivalent to buying and selling every day , namely Pn−P1=(P2−P1)+(P3−P2)+…+(Pn−Pn−1)
3. Continuous decline in trading days ： Then the trading income is the largest , That is, you won't lose money

Summary can be obtained ： Since the number of transactions is not considered . Let's consider the stock price of the next two days , If the stock price of the next day is greater than that of the previous day , Then after the buy and sell operation , You can make a profit . Such greed will certainly make the greatest profit .

Directly traverse the entire array . If prices[i+1]-prices[i] Greater than 0, Then add the final total profit .

3. Code

class Solution {
    
public:
    int maxProfit(vector<int>& prices) {
    
        int res=0;
        for(int i=0;i<prices.size()-1;i++){
    
            res+=max(0,prices[i+1]-prices[i]);
        }
        return res;
    }
};