1
00:00:00,810 --> 00:00:02,070
Welcome to this video.

2
00:00:02,220 --> 00:00:05,400
In this video, you're going to sow discord are going to be caution.

3
00:00:05,880 --> 00:00:08,940
Best time to buy and sell stock, too.

4
00:00:10,320 --> 00:00:13,800
In this problem we're given an array of integers.

5
00:00:14,280 --> 00:00:19,890
Is integers represent the price of a stock at a certain date.

6
00:00:20,790 --> 00:00:24,540
This integer seven indicates the price of a stock.

7
00:00:24,660 --> 00:00:26,580
At first it is one.

8
00:00:27,990 --> 00:00:29,790
This integer seven represents.

9
00:00:30,600 --> 00:00:34,710
This integer seven means the price of a stock.

10
00:00:34,710 --> 00:00:38,100
At this D one is seven.

11
00:00:38,130 --> 00:00:39,120
This is dear one.

12
00:00:39,690 --> 00:00:40,680
This is the index.

13
00:00:40,680 --> 00:00:41,080
Okay.

14
00:00:41,370 --> 00:00:46,290
But this is the one that due to the price is one at three the price.

15
00:00:46,710 --> 00:00:49,110
The price is five and so on.

16
00:00:50,100 --> 00:00:53,970
Now we have to return the maximum profit we can meet.

17
00:00:54,120 --> 00:00:57,780
We can engage in multiple transactions.

18
00:00:57,960 --> 00:01:01,530
We can make transactions as many times as we want.

19
00:01:01,860 --> 00:01:05,040
We cannot made multiple transactions simultaneously.

20
00:01:05,050 --> 00:01:07,470
We have to sell the stock before buy one.

21
00:01:07,900 --> 00:01:08,310
Okay.

22
00:01:08,730 --> 00:01:15,540
So if we buy at these pride and if we sell at this price, it will have the profit for.

23
00:01:15,810 --> 00:01:21,780
And if we buy at this price and the sale at this price, we'll have the profit three.

24
00:01:22,350 --> 00:01:26,010
So the maximum profit we can made is seven.

25
00:01:26,340 --> 00:01:30,630
So for this, given ali of integers, we have to read in seven.

26
00:01:31,680 --> 00:01:39,250
For example, if we we're given these area of integers we know is integers represents the pride of a

27
00:01:39,270 --> 00:01:39,810
stock.

28
00:01:40,380 --> 00:01:42,780
The up look at this one is one.

29
00:01:42,780 --> 00:01:45,910
The price of stock at the two is two.

30
00:01:45,930 --> 00:01:47,670
And so what now?

31
00:01:47,670 --> 00:01:57,450
If we if we buy at price one and if we sell at price to have the profit to one, if we buy at two and

32
00:01:57,450 --> 00:02:01,370
if we sell at three, we will have we will have profit one.

33
00:02:01,380 --> 00:02:04,920
If we buy at three, if we sell at four, we will have profit one.

34
00:02:05,910 --> 00:02:08,610
If we buy it for every sale at five, we will have profit of one.

35
00:02:08,610 --> 00:02:12,420
And if we buy it five, and if we sell at six, we will have profit one.

36
00:02:12,870 --> 00:02:17,310
We cannot engage in multiple transaction simultaneously.

37
00:02:17,430 --> 00:02:20,820
We have to sell the stock before buy one.

38
00:02:20,970 --> 00:02:26,760
Okay, so we are selling it two under buying at two, it's allowed.

39
00:02:27,060 --> 00:02:31,260
So for this given area of integers, we have to return five.

40
00:02:31,650 --> 00:02:32,610
This is the problem.

41
00:02:32,610 --> 00:02:34,590
Now, how to solve this problem?

42
00:02:34,920 --> 00:02:37,410
This problem actually pretty straightforward.

43
00:02:37,890 --> 00:02:40,860
To understand this problem, let's draw a graph.

44
00:02:40,860 --> 00:02:42,660
You can look at a graph.

45
00:02:42,930 --> 00:02:46,560
Then this problem becomes so easy to understand.

46
00:02:47,400 --> 00:02:49,350
Now let's draw a graph.

47
00:02:49,950 --> 00:02:51,570
This is the graph for this area.

48
00:02:51,570 --> 00:02:53,970
And this is the graph for this area.

49
00:02:54,840 --> 00:02:56,940
This graph for this area.

50
00:02:56,940 --> 00:02:59,220
And this graph for these areas.

51
00:02:59,880 --> 00:03:03,150
Now, if we compare is here we have 7.1.

52
00:03:03,150 --> 00:03:07,710
We see seven on high price and one at low price.

53
00:03:08,010 --> 00:03:11,400
So we cannot buy at seven and we cannot sell that one.

54
00:03:11,700 --> 00:03:15,750
Now let's compare this pair since you are allowed multiple transaction.

55
00:03:16,890 --> 00:03:18,540
So here we see this is low, right?

56
00:03:18,540 --> 00:03:19,400
And this is a high price.

57
00:03:19,400 --> 00:03:25,560
So if we buy here and if we sell here, we can gain oh, we can make some profit.

58
00:03:25,800 --> 00:03:27,180
So we'll have the profit here.

59
00:03:27,180 --> 00:03:28,650
Five minus one is four.

60
00:03:29,160 --> 00:03:33,000
Now we see this is decreasing in this pair.

61
00:03:33,000 --> 00:03:33,960
We cannot buy here.

62
00:03:33,960 --> 00:03:35,040
We cannot sell here.

63
00:03:35,640 --> 00:03:37,860
If we do that, we'll have a lot.

64
00:03:38,460 --> 00:03:42,600
Now, if we buy here, if we sell here, you'll have some profit.

65
00:03:43,020 --> 00:03:46,650
That is six minus three, which is three.

66
00:03:46,860 --> 00:03:52,530
And if you compare this pair, we see that we'll have some lot if we buy here and if we sell here.

67
00:03:52,800 --> 00:03:59,910
So we have to do profit here savvy by looking at this graph, we see that if we compare is here, if

68
00:03:59,910 --> 00:04:09,120
we buy at a lower price and if we sell at high price for is here, then it can make the maximum profit

69
00:04:09,330 --> 00:04:10,470
for this area.

70
00:04:10,740 --> 00:04:13,410
If we buy here, we sell her, we will have profit one.

71
00:04:13,830 --> 00:04:17,880
If we buy here, if we sell here, you'll have profit one and so on.

72
00:04:18,270 --> 00:04:22,380
Okay, so we can made here to grow FY profit.

73
00:04:23,130 --> 00:04:29,040
This is how we can solve this problem first and compared this we see decreasing, not increasing.

74
00:04:29,040 --> 00:04:31,410
So will not buy at lift and not sell here.

75
00:04:31,740 --> 00:04:36,780
Then for this pier we will buy here and will sell here because this is increasing.

76
00:04:37,230 --> 00:04:41,700
Now here we see for this to appear two will unit buy at five will not select three.

77
00:04:41,970 --> 00:04:45,440
Then for this pier it's increasing so we can buy it.

78
00:04:45,480 --> 00:04:47,460
You can select six been here.

79
00:04:47,460 --> 00:04:52,390
We see that we cannot buy at six and we cannot sell it for.

80
00:04:52,680 --> 00:04:56,790
So this is our increasing portion increasing pier.

81
00:04:57,090 --> 00:04:59,790
So for this to appear to be made to.

82
00:04:59,860 --> 00:05:01,790
Transaction will have maximum profits.

83
00:05:01,790 --> 00:05:07,090
Seven four is coming from here and three is coming from here.

84
00:05:07,930 --> 00:05:10,030
So four plus three equals two seven.

85
00:05:11,350 --> 00:05:13,660
So for this given input, we should return seven.

86
00:05:13,990 --> 00:05:21,640
And for this period we see every single power in increasing order, every single peer so we can meet

87
00:05:21,640 --> 00:05:28,900
here to do five profits by buying and selling at is pair.

88
00:05:29,650 --> 00:05:31,090
This is how we can solve this problem.

89
00:05:31,090 --> 00:05:33,430
In that case, we have to scan the tariff once.

90
00:05:33,850 --> 00:05:38,860
So the time complexity is of in and this space complexity is of one.

91
00:05:39,580 --> 00:05:45,370
No, let's write out the code now let's implement our algorithm first.

92
00:05:45,370 --> 00:05:47,740
Let's create a variable profit equals to zero.

93
00:05:47,770 --> 00:05:49,600
Our initial profit is zero.

94
00:05:50,020 --> 00:05:57,940
Now I'm going to iterate from second element I class to one I liston prices start length I plus but

95
00:05:58,660 --> 00:06:06,970
will have here pair the first limit in the period at index I minus one and add index I so let's compare

96
00:06:07,660 --> 00:06:18,250
if if price which I minus one is less than price which I then let's calculate profit so profit plus

97
00:06:18,250 --> 00:06:29,170
equal to price it I minus prices I minus one at the end will return the profit, the minimum length.

98
00:06:29,200 --> 00:06:30,760
Our prices are going to be one.

99
00:06:31,120 --> 00:06:34,450
If the later prices is one, this loop will not be executed.

100
00:06:34,450 --> 00:06:35,740
It will just return zero.

101
00:06:36,280 --> 00:06:41,830
This algorithm will takes off in time, complexity and of one space complexity.

102
00:06:42,220 --> 00:06:43,930
Now let's run this code.

103
00:06:44,740 --> 00:06:45,550
Accepted.

104
00:06:45,700 --> 00:06:48,160
Let's submit it accepted.

105
00:06:48,160 --> 00:06:49,540
We have solved this problem.

106
00:06:49,720 --> 00:06:51,580
Thanks for watching this video.