当前位置:网站首页>Leetcode notes - dynamic planning -day7
Leetcode notes - dynamic planning -day7
2022-07-06 15:16:00 【LL. LEBRON】
List of articles
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
- Observe carefully
a[i] + a[j] + i - j
, Decomposable into :(a[j]-j)+(a[i]+i)
- Again because
i<j
, We canj
As current point , So we only need to traverse this problem . Use a variablef
maintainj
All before the dota[i]+i
The maximum of 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
- Use a variable
minn
maintain[0,i-1
] The minimum price of - Enumerate to
i
when ,prices[i]-minn
It means the current pointi
The biggest gain from selling - 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 :
- 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 )
- 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)
- 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;
}
};
边栏推荐
- MySQL数据库(二)DML数据操作语句和基本的DQL语句
- 软件测试需求分析之什么是“试纸测试”
- 几款开源自动化测试框架优缺点对比你知道吗?
- Statistics 8th Edition Jia Junping Chapter 4 Summary and after class exercise answers
- Daily code 300 lines learning notes day 9
- Interview answering skills for software testing
- Knowledge that you need to know when changing to software testing
- ucore lab6 调度器 实验报告
- Threads et pools de threads
- Should wildcard import be avoided- Should wildcard import be avoided?
猜你喜欢
Knowledge that you need to know when changing to software testing
MySQL development - advanced query - take a good look at how it suits you
Réponses aux devoirs du csapp 7 8 9
Cadence physical library lef file syntax learning [continuous update]
Threads et pools de threads
线程及线程池
線程及線程池
Description of Vos storage space, bandwidth occupation and PPS requirements
STC-B学习板蜂鸣器播放音乐
UCORE lab1 system software startup process experimental report
随机推荐
Sleep quality today 81 points
Oracle foundation and system table
Build your own application based on Google's open source tensorflow object detection API video object recognition system (II)
Global and Chinese market of DVD recorders 2022-2028: Research Report on technology, participants, trends, market size and share
[Ogg III] daily operation and maintenance: clean up archive logs, register Ogg process services, and regularly back up databases
Servlet
Investment should be calm
STC-B学习板蜂鸣器播放音乐
转行软件测试必需要知道的知识
[200 opencv routines] 98 Statistical sorting filter
Nest and merge new videos, and preset new video titles
Example 071 simulates a vending machine, designs a program of the vending machine, runs the program, prompts the user, enters the options to be selected, and prompts the selected content after the use
How to become a good software tester? A secret that most people don't know
C4D quick start tutorial - Introduction to software interface
Threads and thread pools
UCORE LaB6 scheduler experiment report
China's county life record: go upstairs to the Internet, go downstairs' code the Great Wall '
Mysql database (II) DML data operation statements and basic DQL statements
Common Oracle commands
MySQL数据库(二)DML数据操作语句和基本的DQL语句