1
00:00:00,930 --> 00:00:02,550
Hi, everyone, welcome back.

2
00:00:02,580 --> 00:00:07,880
So in this video, we are going to discuss one very important question, which is the maximum Zebedee.

3
00:00:08,430 --> 00:00:09,800
So the question is very simple.

4
00:00:09,840 --> 00:00:12,710
You are given Manetti, this is 180 fine.

5
00:00:13,410 --> 00:00:15,540
What do you need to do in order to find out?

6
00:00:15,840 --> 00:00:16,790
One contiguous.

7
00:00:16,790 --> 00:00:21,360
Sabeti Not one year to find out the contiguous Sabari which has the maximum sum.

8
00:00:22,770 --> 00:00:30,860
So in this area, if we talk or let's talk about this area so the Sabeti can be five, this can be five

9
00:00:30,900 --> 00:00:35,100
and for the next Sabeti can be five for minus one.

10
00:00:36,750 --> 00:00:40,290
Next subarea can be five for minus one seven.

11
00:00:40,560 --> 00:00:45,220
Knecht Sabeti can be five for minus one seven eight eight.

12
00:00:45,270 --> 00:00:52,950
And then the next Cybertech and before then it can be four minus one, then it can be four minus one

13
00:00:53,160 --> 00:00:57,210
seven, then it can be four minus one seven eight.

14
00:00:57,810 --> 00:01:04,769
Then next can be basically minus one, then it can be minus one seven, then it can be minus one seven,

15
00:01:04,769 --> 00:01:05,810
eight and so on.

16
00:01:05,820 --> 00:01:06,660
You got my point.

17
00:01:06,880 --> 00:01:11,220
So we have multiple samaris multiple contiguous Cibeles.

18
00:01:12,330 --> 00:01:16,440
So out of all these possible contiguous savary, what do we need to do?

19
00:01:16,450 --> 00:01:20,940
We need to find out the sum of all other matters and it would take the maximum.

20
00:01:21,630 --> 00:01:24,930
So in this case, it is saying the maximum sum is twenty three.

21
00:01:25,290 --> 00:01:29,730
So how make some some can be grown bedri in this savary if we will pick this Sabari.

22
00:01:31,290 --> 00:01:37,620
If we will fix this better than the sum of all the elements came out of it or the 380 is the largest

23
00:01:37,620 --> 00:01:43,740
sum in this case, there will be many samaris, but we are only interested in that.

24
00:01:43,740 --> 00:01:47,340
Sabeti, which has the maximum sum and we need to return the maximum sum.

25
00:01:47,340 --> 00:01:51,210
So this subarea has the maximum sum, which is six, right.

26
00:01:51,210 --> 00:01:51,750
This one.

27
00:01:54,290 --> 00:01:56,320
So we need to get it done this summer.

28
00:01:57,260 --> 00:02:01,650
Now, how we can solve this question, so first approach is very simple like this, right?

29
00:02:03,170 --> 00:02:03,830
What do you do?

30
00:02:04,010 --> 00:02:07,640
You tend to lose in this case, you will run to loop.

31
00:02:08,960 --> 00:02:11,430
So in the outer loop, you will fix the element.

32
00:02:11,450 --> 00:02:18,980
For example, I will fix element five and in the inner loop, you will I over all the elements and you

33
00:02:18,980 --> 00:02:20,210
will add the values.

34
00:02:20,210 --> 00:02:20,510
Right.

35
00:02:20,510 --> 00:02:25,700
You will add values and then you will maintain one variable, which is the maximum sum.

36
00:02:25,970 --> 00:02:31,270
And if the sum of the error, if the sum of the SABERA is greater than the maximum sum, you update

37
00:02:31,280 --> 00:02:32,000
the maximum.

38
00:02:32,270 --> 00:02:37,340
So in this case, when you consider each and every SABERA and find out the sum your time complexity

39
00:02:37,340 --> 00:02:39,370
will be, you will be using two loops.

40
00:02:39,380 --> 00:02:44,990
So time complexity for considering all the subsidies will be big off and square and space will be big.

41
00:02:44,990 --> 00:02:47,070
Often you will be creating very few variables.

42
00:02:48,950 --> 00:02:51,080
So this is the time and the space complexity.

43
00:02:51,080 --> 00:02:51,410
Right.

44
00:02:51,640 --> 00:02:56,910
But what we want we want to solve this problem in big off in time and constraint space.

45
00:02:57,350 --> 00:03:02,900
So this is this can be achieved with the help of an algorithm, which is Koran's algorithm.

46
00:03:04,040 --> 00:03:11,600
So Caden's algorithm helps us in finding out the maximum some sabari and how cadenced algorithm works.

47
00:03:11,630 --> 00:03:19,350
So let me explain to you, so what happens in condensed algorithm is basically as soon as you son your

48
00:03:19,350 --> 00:03:23,750
current sum becomes negative, you will make your current sum to be zero.

49
00:03:25,460 --> 00:03:27,560
This is what this algorithm does.

50
00:03:27,560 --> 00:03:31,750
If the current sum is negative, then Makarand equals to zero.

51
00:03:32,180 --> 00:03:36,390
So let's use credential Vadum on this and how it will work.

52
00:03:36,890 --> 00:03:40,580
So initially my maximum sum, what is my maximum sum.

53
00:03:40,580 --> 00:03:45,690
So make some sum essentially the same minus infinity rate so it will be delighted with the idea.

54
00:03:46,580 --> 00:03:47,390
Let's do it.

55
00:03:47,670 --> 00:03:49,060
So minus two.

56
00:03:49,070 --> 00:03:49,820
So what do do.

57
00:03:51,600 --> 00:03:57,410
Current term is initially zero, and you will add the current element of the added to the current,

58
00:03:57,570 --> 00:04:02,280
so current sum will become minus two rate, you will add minus two to zero.

59
00:04:02,430 --> 00:04:03,880
So current sum is minus two.

60
00:04:04,170 --> 00:04:05,100
Then we will compare.

61
00:04:05,100 --> 00:04:07,980
So minus two and infinity, which one is bigger?

62
00:04:08,310 --> 00:04:09,340
Current sum is bigger.

63
00:04:09,360 --> 00:04:11,700
So will update minus infinity to minus two.

64
00:04:13,140 --> 00:04:22,140
So what I'm writing here is so if basically the current sum just write like this, what is the maximum

65
00:04:22,140 --> 00:04:22,410
sum.

66
00:04:22,890 --> 00:04:31,580
Maximum sum is the maximum of the current maximum sum and the current rate.

67
00:04:31,680 --> 00:04:32,970
So this was minus infinity.

68
00:04:33,000 --> 00:04:38,770
This is minus two and you will update minus infinity to minus two decision maximum now.

69
00:04:39,450 --> 00:04:45,790
And remember, this condition to current sum is minus of two, so we'll again make it zero.

70
00:04:46,080 --> 00:04:50,070
So again, the current sum zero next element is one.

71
00:04:50,070 --> 00:04:51,810
So add one to current sum.

72
00:04:52,050 --> 00:04:58,150
So zero plus one is when No one and minus two, which one is bigger, one is bigger.

73
00:04:58,470 --> 00:05:00,260
So we will make it one.

74
00:05:00,420 --> 00:05:06,300
And this condition so current sum is positive, will move on to the next element minus three.

75
00:05:07,320 --> 00:05:08,760
So what is minus three.

76
00:05:09,060 --> 00:05:10,460
Will add minus three here.

77
00:05:11,220 --> 00:05:11,480
Right.

78
00:05:11,730 --> 00:05:12,900
So one minus three.

79
00:05:13,140 --> 00:05:15,590
The current sum becomes minus two again.

80
00:05:15,870 --> 00:05:17,970
So minus two and one which one is bigger.

81
00:05:17,970 --> 00:05:19,740
One is bigger, do nothing.

82
00:05:20,070 --> 00:05:24,090
And here the current sum becomes less than zero minus two.

83
00:05:24,360 --> 00:05:25,620
So we'll again make it zero.

84
00:05:25,710 --> 00:05:28,280
So we will again make the current term to be zero.

85
00:05:29,250 --> 00:05:29,580
Fine.

86
00:05:30,300 --> 00:05:33,270
Now the next element is four.

87
00:05:33,450 --> 00:05:37,590
So before considering this next element, let's say you have only this Sabeti.

88
00:05:37,950 --> 00:05:39,540
You have only this at a rate.

89
00:05:39,960 --> 00:05:43,170
You have an array which is containing minus one and minus three.

90
00:05:43,170 --> 00:05:44,550
And what is your maximum some?

91
00:05:45,090 --> 00:05:48,330
This algorithm is saying maximum is one and one is the right answer.

92
00:05:48,330 --> 00:05:48,710
Right?

93
00:05:49,110 --> 00:05:52,410
If we consider only this area, then one is the maximum.

94
00:05:53,040 --> 00:05:56,650
So basically this is the proof that this algorithm is working now.

95
00:05:56,670 --> 00:05:58,080
The next element is four.

96
00:05:58,470 --> 00:06:00,300
So zero plus four will be four.

97
00:06:00,810 --> 00:06:04,720
So current sum is four now compared for anyone, four is bigger.

98
00:06:05,100 --> 00:06:09,110
So will update make some some two four and current some is positive.

99
00:06:09,120 --> 00:06:10,950
So do nothing now in this case.

100
00:06:10,980 --> 00:06:18,780
Also if we consider this area, then what is the maximum sum for what is the maximum sum rate.

101
00:06:19,080 --> 00:06:22,940
So again, this is the proof that our algorithm is working now.

102
00:06:22,950 --> 00:06:24,720
The next element is minus one.

103
00:06:25,260 --> 00:06:30,330
So four minus one will be three, be three and four, which is bigger.

104
00:06:30,570 --> 00:06:31,300
Four is bigger.

105
00:06:31,320 --> 00:06:31,980
So do nothing.

106
00:06:32,280 --> 00:06:34,330
Current sum is positive, so do nothing.

107
00:06:35,070 --> 00:06:36,840
Now the next element is two.

108
00:06:37,980 --> 00:06:40,150
So three plus two it will become five.

109
00:06:40,200 --> 00:06:42,000
So five and four, which one is maximum.

110
00:06:42,000 --> 00:06:42,960
Five is maximum.

111
00:06:42,960 --> 00:06:46,760
So updated to five and current sum is positive.

112
00:06:46,770 --> 00:06:49,010
So do not think next element is one.

113
00:06:49,030 --> 00:06:54,030
So five plus one it will become six six and five six is maximum.

114
00:06:54,030 --> 00:06:58,090
So update it to six and current seven is positive, so do nothing.

115
00:06:58,110 --> 00:07:02,940
So next element is minus five, so six minus five it will become one.

116
00:07:03,150 --> 00:07:03,960
One in six.

117
00:07:04,380 --> 00:07:06,030
Six is greater than one.

118
00:07:06,060 --> 00:07:08,530
So do not think algorithm is positive, so do nothing.

119
00:07:08,970 --> 00:07:10,480
Next element is four.

120
00:07:10,770 --> 00:07:15,150
So one plus four it will become five, five and six which was this maximum.

121
00:07:15,150 --> 00:07:16,250
Six is maximum.

122
00:07:16,260 --> 00:07:18,500
So do nothing and is positive.

123
00:07:18,630 --> 00:07:24,570
So do nothing and we will reach the end of the array and the maximum you have is six and six is the

124
00:07:24,570 --> 00:07:25,210
right answer.

125
00:07:25,860 --> 00:07:27,960
So that's how it works, right.

126
00:07:30,130 --> 00:07:34,120
In this case, also, let's do it quickly.

127
00:07:34,300 --> 00:07:35,650
So what is maximum sum?

128
00:07:35,650 --> 00:07:37,050
It is minus infinity.

129
00:07:37,570 --> 00:07:38,770
What is current?

130
00:07:38,770 --> 00:07:43,360
Some obviously it will be zero initially and we need to remember this condition.

131
00:07:45,780 --> 00:07:52,500
So let's start and let's do it quickly, so five zero plus five, it will become five five and infinity

132
00:07:52,800 --> 00:07:59,330
five and minus infinity, so five is greater and continues positive guidance is positive to nothing.

133
00:07:59,610 --> 00:08:03,900
Next element is four five plus four nine nine is lower than five.

134
00:08:03,900 --> 00:08:09,450
Subnet and Grantham's positive do nothing next element minus one nine minus on it.

135
00:08:09,600 --> 00:08:10,780
So nine is good than it.

136
00:08:10,800 --> 00:08:12,900
Do nothing continuous positive.

137
00:08:12,930 --> 00:08:13,440
Do nothing.

138
00:08:13,440 --> 00:08:15,240
Seven, eight plus seven.

139
00:08:15,270 --> 00:08:16,260
It will become fifteen.

140
00:08:16,260 --> 00:08:16,560
Fifteen.

141
00:08:16,560 --> 00:08:23,760
These are the nine updated to fifteen and it is positive do nothing it so fifteen plus eight.

142
00:08:23,760 --> 00:08:24,390
Twenty three.

143
00:08:24,390 --> 00:08:25,740
Twenty three is greater than fifteen.

144
00:08:25,750 --> 00:08:27,930
So update twenty three is positive.

145
00:08:27,930 --> 00:08:29,910
Do nothing you will reach the end.

146
00:08:30,180 --> 00:08:32,940
The maximum is on the tree and that is your right answer.

147
00:08:33,570 --> 00:08:33,960
Right.

148
00:08:34,409 --> 00:08:38,880
So in this case what we are doing, we are iterating over the area only once.

149
00:08:39,570 --> 00:08:45,060
So time complexity is big often and we are creating a few variable current and make some, some space

150
00:08:45,060 --> 00:08:46,500
complexity will be big often.

151
00:08:46,890 --> 00:08:54,190
So this is your time complexity, this is your space complexity and that is our guidance algorithm and

152
00:08:54,240 --> 00:08:55,890
that is our guidance algorithm.

153
00:08:56,190 --> 00:08:59,520
So in next video, we will be writing the code for guidance algorithm.

154
00:08:59,520 --> 00:09:02,040
But this code is going to be very, very simple.

155
00:09:02,040 --> 00:09:06,870
So I highly recommend that you must implement this code yourself.

156
00:09:06,870 --> 00:09:07,410
Right.

157
00:09:07,410 --> 00:09:10,950
And if you face any difficulty, then watch the solution in the next one.

158
00:09:10,950 --> 00:09:12,480
So I will see you in the next video.

159
00:09:12,480 --> 00:09:13,020
Thank you.