In the 3rd METHOD...you need to take MAX(inversion_answer, Kadane's_answer) to get correct result. This i have explained for 4th METHOD where i implemented the logic of Kadane's algorithm. The aim of first 3 methods was just to give you an idea about other possible solutions and hence are not explained in depth :)
Yes , For this method's there will be two possibilities either we will requires Wrapping or not ... So you have explained only that case when we will require Wrapping but for the non wrapping case we also have to calculate the max_sum_subarray for the normal array too... And then maximum of the two will be our answer :)
@@harshithmundada5100 MAX(inversion_answer, Kadane's_answer) before cheeking this condition you have to check if inversion_answer == 0 then our answer will be kadane`s _answer, other wise return MAX(inversion_answer, Kadane's_answer).
We have a new baller in town! What sets you apart from others is you start explaining from the most basic naive solution, all the way to the most effective solution. Please keep doing that. Everyone can explain the solution, but that is not what we need. How to approach to the solution is key, you are killing it. Huge fan! Thank you very much!
Actually there is a mistake in the solution, You need to take the maximum of kadane's algo and inverted kadane's where I mean by inverted kadane's is the third method explained in the video.
Actually the 2 cases were shown properly in 4th method. The first 3 methods were just alternate solution ideas because I only implemented the 4th method. In the 1st and 2nd method it was not required but in the 3rd method we need to take max of both the cases as pointed out by you (like we did in method 4). Thanks.
@@techdose4u Here is the C++ code class Solution { public: int maxSubarraySumCircular(vector& A) { int n=A.size(); int curr_sum=A[0], max_sum=A[0]; for(int i=1;i
@@KoushikChowdhury2016 it is not compiled. I counted 4 syntax mistakes. Even after fixing mistakes it gives a wrong answer for [-2,-3,-1]. Also the solution has many loops. The answer can be calculated using 1 loop.
sir you mentioned in the second solution that the max subarray sum is total array sum - min subarray sum. But I guess it should be max( maximum subarray sum using kadane's Algo, total array sum - min subarray sum). Because then only the algo will work properly on test cases like 1, -2, 3, -2. Please correct if I am wrong. Thanks!
he is right bro and you are wrong. At first you have to calculate total sum of that array which is 0 in your test case then you have to subtract the minimum subarray value which is -2 in your test case so 0-(-2)=2 . and it is the answer. You cant go to the first position from last position while you are calculating minimum subarray value.
I had implemented 2nd solution and came up with first 3 solutions but the 2nd solution code looked messy. I saw 4th solution and again implemented the question using 4th one :D I hope these techniques were helpful.
Not sure the changing sign method works for every case. You mentioned one of the boundary cases when all the elements are negative. The counterpart to that would be when all are positive too, we should sum everything up. However, there is still one case that I am struggling to wrap my head around: eg (-2,3,-2). According to your solution, we would get 1, but the actual solution is 3. Let me know if I am missing something. Removing only one instance of the min sub-array (if there are multiple instances) will not suffice.
demystify Confusion :The ans = array_sum - min_sub_array_sum is incomplete so to say, Consider this test cased (listed on leet code) : [1, -2, 3, -2] ans should be 3 but as per above explained algo its coming 2. Now, to handle this we can say my final ans should be max(array_sum - min_sub_array_sum, max_sub_array_sum) Also as explained correctly in video there is edge case (all negative elements) in this case return max value. y Yes, we can traverse only once and do all the checks/computation in single pass, nothing spl. TC O(n) SC O(1) solution : int maxSubarraySumCircular(vector& nums) { int local_min(nums[0]),global_min(nums[0]); int local_max(nums[0]),global_max(nums[0]); int total_sum = nums[0]; int negEleCount = nums[0] < 0 ? 1 : 0; int largestElement = nums[0]; for(int i=1;i
Hello Mahnaz, Could you please help me to understand Sol-2, "Find Max SubArray Sum with Max Window Size-N", I could not understand his approach- How he is moving Left and Right pointers. Thank You in Advance
Okay. Great video. Though i have some queries. 1. In solution 3, instead of inverting numbers(which confuses me) , we could tweak kadane's algo to find the min subarray sum. That sould work right as per the observations at 05:05 2. If my input is [-1, 5, 5, - 1] Min subarray sum = - 1 Total array sum = 8 Hence, max subarray sum = 8-(-1) = 9 Shouldn't the answer be 10?
You have to find the max sum using kadanes algo ,and compare that max sum with the max sum via his approach, and return max ,out of both. Here max sum kadanes algo 5+5 =10 Tech dose explanation: Sum of total array =8 Invert signs and find max sum subarray we get 1 as the value. (sum-invert val) = 8-1 =7 Max(10,7) =10
Hello Raja, Could you please help me to understand Sol-2, "Find Max SubArray Sum with Max Window Size-N", I could not understand his approach- How he is moving Left and Right pointers. Thank You in Advance
explanation was really osm ...But sir Some test cases fail when i used MAX(inversion_answer, Kadane's_answer) in third method.I hope everyone finds third one to be ec,can u pls code third one in c++ :)
[-5, 1, -5] Here min-straight-sum = total sum = -9. But from this we can not say that all elements are negative. I think your method 4 need to be updated.
what if minimum sub array sum is in circular subarray like - [1,-2,3,-2]? min sub array sum = -2 and total is 0 so answer=>total - min sub array sum= 0-(-2)= 2 which is wrong !! Correct answer is 3!!! Plz help me understand this? Who else came here to solve after seeing 18 th jan problem of day?? :)
Lot of people getting confused about method 3, I have implemented it as explained(with correction), it's a nice approach, kudos to @TECHDOSE , here is the solution using method 3. I know I used some extra space, but it looks more clear this way! int maxSubarraySumCircular(vector& A) { int sz=A.size(); bool allNegative=true; int totalSum=A[0],minAns=A[0],maxAns=A[0],maxallNegative=A[0]; int dp1[sz],dp2[sz]; memset(dp1,0,sizeof(dp1)); memset(dp2,0,sizeof(dp2)); dp1[0]=A[0],dp2[0]=A[0]; if(A[0]>0) allNegative=false; for(int i=1;i0) allNegative=false;
It the answer is within the initial array then the answer would be maximum sum subarray, therefore the max(max_Straight_sum, total_sum - min_straight_Sum) is taken. Watch from 1:10
Idea for method 3 and 4 are same. Maximum sum subarray = Array sum - minimum sun subarray (with boundary cases as exceptions). Now, array sum is easy to find. How do you find min sum subarray? You can use kadane's algorithm only to find max and not min. So if you invert sign of every number then the problem changes to finding max sum subarray. Find using kadane's and again invert the sum result to get your min sum subarrays value. You have array sum as well. So, max sum subarray with wrap around is easy breezy now :)
@@techdose4u U went off-topic he and even I am asking now, how is it working. How doing like that is giving us the correct answer PS: I am not asking to explain your approach or the algorithm run through. Maximum sum subarray = Array sum - minimum sun subarray (with boundary cases as exceptions). This we can do for standard max sum subarray question right so why are we using the other algo instead of this(I mean the same algo with the different idea) and why this now and how did u get this.
Can you please tell me why this is failing test cases when I followed method 3 and even used max(inversion_answer, Kadane's_answer) public static void main (String[] args)throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int cases = Integer.parseInt(br.readLine().trim()); while(cases-->0){ int n = Integer.parseInt(br.readLine().trim()); int[] arr = new int[n]; int arrSum = 0; String ip[] = br.readLine().trim().split(" "); for(int i=0;i
thanks a lot for explanation, when you discuss the third method i thought this is it but there is an extra chk which you discuss later on. i.e. which of the two is max normal kadane's or wrapping part.
It is very logical na. It was sure that you needed to use kadane's. Some other questions also use these observations. So, if you have seen those questions or solutions then probably this will also natural come to mind. As I keep saying, it's all about practice.
Third method: (JAVA) class Solution { public int maxSubarraySumCircular(int[] nums) { int n=nums.length; int minS=100000; int maxS=-100000; int currMaxS=0; int currMinS=0; int total=0; boolean check=false; boolean allNegative=true; for(int i=0;i=0) allNegative=false; // sum of all numbers total+=nums[i]; // min subarray if(currMinS>0) currMinS=0; currMinS+=nums[i]; minS=Math.min(minS,currMinS); // max subarray if(currMaxS
Hello Carlos, Could you please help me to understand Sol-2, "Find Max SubArray Sum with Max Window Size-N", I could not understand his approach- How he is moving Left and Right pointers. Thank You in Advance
I tried your alternative method and it worked on first go itself. I tried to understand why it works? and failed to understand the logic. could you please help?
For input array (-5, -3, 2, -4) , the above logic not working. Total array sum will be -10 and min array sum will be -10 and if we subtract them -10-(-10) then it equals 0 . But max array sum should be 2. Am I missing anything. Please help
I knew 3 methods. I took the 4th method from best time solution after submitting. I just dry ran on several examples and I explained the logic what I got.I wanted to discard this from including in the video, but I still included it 😅.This type of algos are not algos but tricks and it won't help during interviews. So I am not a fan of method 4. But method 3 is very common and intuitive. Method 3 is very useful for many problems.
In the 2nd method-- min sub-array sum and total array sum if the input is [5,-3,2,-6,-1,4] the min sub array will be =-7 and total sum will be -1 which is equal to -8, which is wrong. XXXXX.
please check ur final soln with arr = [-10,-7,9,-7,6,9,-9,-4,-8,-5] Expected ans: 17, i guess above algo will return 9 won't it be better to keep a boolean variable initially set false 'onePositiveFound' to indicate at least 1 non-negative value was found in the array and return final ans based upon it?
Actually this is working with what I explained. NOTE: You need to take max of both cases. I just showed the first case and missed the 2nd case. The 2 cases are max subarray sum in array without wrap and 2nd one is max subarray sum with wrap around. We take max of both to return as answer. You can see that for method 4 I did include both cases while returning and I explained in code as well. In the same way, you need to do for method 3 as well. I just roughly explained it to give the idea.
Ithink it fails here {4,-1,2,6,-1,7,1,-10,5} suppose this array here min subArraySum =-10 and arrSum=5 now it will give maxSubArraySum=15 but the ans in 9 you should take sum of non-contributing elements instead of minSubArraysum. sum of non-contributing elements=-4 arrSum=5 so ans is 9 which is correct.
I tried option 2. Seemed logical. Until I realized there wasn't a clear solution of what to do when the sum gets reset to 0. The left pointer becomes invalid. Oops! Tried to work around the issue, ended up with a mess.
Hello, Could you please help me to understand Sol-2, "Find Max SubArray Sum with Max Window Size-N", I could not understand his approach- How he is moving Left and Right pointers. Thank You in Advance
This person has just horribly messed up the whole solution! If you are showing multiple approaches, please dont pin rudimentary explanation for something not explained in detail
Here is the C++ code of 3rd Method class Solution { public: int maxSubarraySumCircular(vector& A) { int n=A.size(); int curr_sum=A[0], max_sum=A[0]; for(int i=1;i
In the second solution of min sub-array sum and total array sum if the input is [5,-3,2,-6,-1,4] the min sub array will be =-7 and total sum will be -1 which is equal to -8, which is wrong. XXXXX.
![🔴 ฟุตบอลแชมป์กีฬา 7HD แชมเปียน คัพ 2024 [รอบ 8 ทีมสุดท้าย] - ช่วงบ่าย](http://i.ytimg.com/vi/M0S_ReCIkxg/mqdefault.jpg)
In the 3rd METHOD...you need to take MAX(inversion_answer, Kadane's_answer) to get correct result. This i have explained for 4th METHOD where i implemented the logic of Kadane's algorithm. The aim of first 3 methods was just to give you an idea about other possible solutions and hence are not explained in depth :)
Yes , For this method's there will be two possibilities either we will requires Wrapping or not ...
So you have explained only that case when we will require Wrapping but for the non wrapping case we also have to calculate the max_sum_subarray for the normal array too...
And then maximum of the two will be our answer :)
@@sureshgarg920 thank u boi
Won't the third method fail for [-1,-2,-3]
@@harshithmundada5100 MAX(inversion_answer, Kadane's_answer) before cheeking this condition you have to check if inversion_answer == 0 then our answer will be kadane`s _answer, other wise return MAX(inversion_answer, Kadane's_answer).
We have a new baller in town! What sets you apart from others is you start explaining from the most basic naive solution, all the way to the most effective solution. Please keep doing that. Everyone can explain the solution, but that is not what we need. How to approach to the solution is key, you are killing it. Huge fan! Thank you very much!
Welcome :)
Here i am struggling with thinking single solution, and u came up with 4 solutions 😑😑how ur brain works.
All are kadane's based only 😅
Relatable...
It's a typical solution that we know the answer and solution first and then explain the problem
sir third approach will not work for this test case [1,-2,3,-2]
Actually there is a mistake in the solution, You need to take the maximum of kadane's algo and inverted kadane's where I mean by inverted kadane's is the third method explained in the video.
Actually the 2 cases were shown properly in 4th method. The first 3 methods were just alternate solution ideas because I only implemented the 4th method. In the 1st and 2nd method it was not required but in the 3rd method we need to take max of both the cases as pointed out by you (like we did in method 4). Thanks.
@@techdose4u Here is the C++ code
class Solution {
public:
int maxSubarraySumCircular(vector& A) {
int n=A.size();
int curr_sum=A[0], max_sum=A[0];
for(int i=1;i
@@KoushikChowdhury2016 it is not compiled. I counted 4 syntax mistakes. Even after fixing mistakes it gives a wrong answer for [-2,-3,-1]. Also the solution has many loops. The answer can be calculated using 1 loop.
sir you mentioned in the second solution that the max subarray sum is total array sum - min subarray sum. But I guess it should be
max( maximum subarray sum using kadane's Algo, total array sum - min subarray sum). Because then only the algo will work properly on test cases
like 1, -2, 3, -2. Please correct if I am wrong. Thanks!
he is right bro and you are wrong. At first you have to calculate total sum of that array which is 0 in your test case then you have to subtract the minimum subarray value which is -2 in your test case so 0-(-2)=2 . and it is the answer. You cant go to the first position from last position while you are calculating minimum subarray value.
this is a great video . I actually did this problem by making prefix sum array but actually waiting for your video for some more approachs
Thanks :)
Could you share with your prefix array solution.please?
really nice. I liked that changing sign solution. You are great, you came up with these many solutions.
I had implemented 2nd solution and came up with first 3 solutions but the 2nd solution code looked messy. I saw 4th solution and again implemented the question using 4th one :D I hope these techniques were helpful.
Not sure the changing sign method works for every case. You mentioned one of the boundary cases when all the elements are negative. The counterpart to that would be when all are positive too, we should sum everything up. However, there is still one case that I am struggling to wrap my head around: eg (-2,3,-2). According to your solution, we would get 1, but the actual solution is 3. Let me know if I am missing something. Removing only one instance of the min sub-array (if there are multiple instances) will not suffice.
demystify Confusion :The ans = array_sum - min_sub_array_sum is incomplete so to say,
Consider this test cased (listed on leet code) : [1, -2, 3, -2] ans should be 3 but as per above explained algo its coming 2.
Now, to handle this we can say my final ans should be max(array_sum - min_sub_array_sum, max_sub_array_sum)
Also as explained correctly in video there is edge case (all negative elements) in this case return max value.
y Yes, we can traverse only once and do all the checks/computation in single pass, nothing spl.
TC O(n) SC O(1) solution :
int maxSubarraySumCircular(vector& nums) {
int local_min(nums[0]),global_min(nums[0]);
int local_max(nums[0]),global_max(nums[0]);
int total_sum = nums[0];
int negEleCount = nums[0] < 0 ? 1 : 0;
int largestElement = nums[0];
for(int i=1;i
Wonderful explanation! It's rare to find such well-elaborated content regarding coding questions on YT, so it's great you are doing so good in it
In your alternative method I guess you forgot to tell one thing if. Temp_maxsum
Maybe 😅 Is it present in code?
@@techdose4u ohh my bad you are making tempsum=0 if sum negetive that will do the trick.sorry.
Thanks for great effort. Something that is missing is WHY any of these methods are "correct".
Hello Mahnaz, Could you please help me to understand Sol-2, "Find Max SubArray Sum with Max Window Size-N", I could not understand his approach- How he is moving Left and Right pointers. Thank You in Advance
amazing ...i learnt 2 new methods today
Nice :)
I understood your explanation very well, but what gives the intuition to approach this problem like this. please help me develop such intuition
Okay. Great video. Though i have some queries.
1. In solution 3, instead of inverting numbers(which confuses me) , we could tweak kadane's algo to find the min subarray sum. That sould work right as per the observations at 05:05
2. If my input is [-1, 5, 5, - 1]
Min subarray sum = - 1
Total array sum = 8
Hence, max subarray sum = 8-(-1) = 9
Shouldn't the answer be 10?
Thanks. Please read the pinned COMMENT by me. You will get your answer :)
You have to find the max sum using kadanes algo ,and compare that max sum with the max sum via his approach, and return max ,out of both.
Here max sum kadanes algo 5+5 =10
Tech dose explanation:
Sum of total array =8
Invert signs and find max sum subarray we get 1 as the value.
(sum-invert val) = 8-1 =7
Max(10,7) =10
@@SinghFlex thanks for the clear explanation !! there's a mistake thought (sum-invert val)=8-(-1)=9 should be the correct thing.
@@SinghFlex Dude...What an explanation 🙌🙌Thanks
best explanation of this problem. thank you
Method 2 does'nt seem to work on testcase : [1,-2,3,-2], Expected answer is 3. but we get 0(total sum) - -2(maxNegative). so we end up getting 2.
return max(maxssum,arsum-minssum);
you can return this instead to get correct answer
Hello Raja, Could you please help me to understand Sol-2, "Find Max SubArray Sum with Max Window Size-N", I could not understand his approach- How he is moving Left and Right pointers. Thank You in Advance
@@SumitSharma-cq2cf It's a sliding window technique. It is a very famous technique. Just google it.
@@rajaganji7982 Sure Thank You I will check this
explanation was really osm ...But sir Some test cases fail when i used MAX(inversion_answer, Kadane's_answer) in third method.I hope everyone finds third one to be ec,can u pls code third one in c++ :)
I think some people have already done it. So have a look at their code. You might understand your mistake.
@@techdose4u thank u so much sir ...u r really too patient to answer all of ur students..hats off:)
Really interesting solution.
Thanks
I actually tried to do the 2nd approach. we have to make sure that we dont process the same element twice.
I also applied the 2nd approach initially 😅
@@techdose4u later you found soln on GFG?
[-5, 1, -5] Here min-straight-sum = total sum = -9. But from this we can not say that all elements are negative. I think your method 4 need to be updated.
irrespective of whether all elements are negative, returning the max_sum value if the condition min_straight_sum == total_sum true works
Nicely explained 😄
Thanks :)
3rd Method
int kadan(vector nums){
int sum=nums[0];
int maxs=nums[0];
int n=nums.size();
for(int i=1;i
👍🏼
what if minimum sub array sum is in circular subarray like - [1,-2,3,-2]?
min sub array sum = -2 and total is 0 so answer=>total - min sub array sum= 0-(-2)= 2 which is wrong !!
Correct answer is 3!!! Plz help me understand this? Who else came here to solve after seeing 18 th jan problem of day?? :)
It's amazing explanation 👍🤩🙏
Lot of people getting confused about method 3, I have implemented it as explained(with correction), it's a nice approach, kudos to @TECHDOSE , here is the solution using method 3. I know I used some extra space, but it looks more clear this way!
int maxSubarraySumCircular(vector& A) {
int sz=A.size();
bool allNegative=true;
int totalSum=A[0],minAns=A[0],maxAns=A[0],maxallNegative=A[0];
int dp1[sz],dp2[sz];
memset(dp1,0,sizeof(dp1));
memset(dp2,0,sizeof(dp2));
dp1[0]=A[0],dp2[0]=A[0];
if(A[0]>0)
allNegative=false;
for(int i=1;i0)
allNegative=false;
dp1[i]=min(dp1[i-1]+A[i],A[i]);
dp2[i]=max(dp2[i-1]+A[i],A[i]);
minAns=min(minAns,dp1[i]);
maxAns=max(maxAns,dp2[i]);
maxallNegative=max(maxallNegative,A[i]);
totalSum+=A[i];
}
if(allNegative)
return maxallNegative;
else
return max(maxAns,(totalSum-minAns));
}
Thanks for sharing
Let's say Kadane's_answer = a, inversion_answer = b, then the corrent answer for the sol. 3 is: a if a < 0 else MAX(a, b).
Yes correct. This is shown in the code for method 4
Great explanation
1st approach index % N will give us end point? if yes then for(int i=0;i
Thank u sir,,, great explanation as usual
Welcome :)
Your explanation could not be any better
Amazing!
Thanks 😊
amazing explanation...can you please tell why we need to take max(max_Straight_sum, total_sum - min_straight_Sum) ?
It the answer is within the initial array then the answer would be maximum sum subarray, therefore the max(max_Straight_sum, total_sum - min_straight_Sum) is taken. Watch from 1:10
YOU ARE JUST AMAZING....MY DREAM TO MEET YOU.
Ok meet-up done ✅
The third method doesn't work for [-3,5,6,-1,4,-2]?
Which method? The 3rd? You need to take max(inversion_answer,kadane's answer)
Ahh I got it. Thank you so much!
Welcome :)
5:32, This dosen't work for all test cases. One of them is {-3, -18, -22, -21, -17, 16, -14, 28, -22}, The correct result is 30.
Amazing solution thanks
outstanding explanation ! Thank you !
what is the idea behind method 3? plzz explain ur thought process
Idea for method 3 and 4 are same. Maximum sum subarray = Array sum - minimum sun subarray (with boundary cases as exceptions). Now, array sum is easy to find. How do you find min sum subarray? You can use kadane's algorithm only to find max and not min. So if you invert sign of every number then the problem changes to finding max sum subarray. Find using kadane's and again invert the sum result to get your min sum subarrays value. You have array sum as well. So, max sum subarray with wrap around is easy breezy now :)
@@techdose4u U went off-topic he and even I am asking now, how is it working. How doing like that is giving us the correct answer
PS: I am not asking to explain your approach or the algorithm run through. Maximum sum subarray = Array sum - minimum sun subarray (with boundary cases as exceptions). This we can do for standard max sum subarray question right so why are we using the other algo instead of this(I mean the same algo with the different idea) and why this now and how did u get this.
you must correct Max sum subarray with max sum circular subbaray
Can you please tell me why this is failing test cases when I followed method 3 and even used max(inversion_answer, Kadane's_answer)
public static void main (String[] args)throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int cases = Integer.parseInt(br.readLine().trim());
while(cases-->0){
int n = Integer.parseInt(br.readLine().trim());
int[] arr = new int[n];
int arrSum = 0;
String ip[] = br.readLine().trim().split(" ");
for(int i=0;i
super brooo
Done!
thanks a lot for explanation, when you discuss the third method i thought this is it but there is an extra chk which you discuss later on. i.e. which of the two is max normal kadane's or wrapping part.
Yea
Very well explained . Thank you so much !
Welcome :)
we have to compare normal kadane answer with the inverted kadane and return maximum of them
Yes correct. This is true for method 3 and 4.
How do you got to the observation that we need to take a difference of total sum with min-sum subarray?
It is very logical na. It was sure that you needed to use kadane's. Some other questions also use these observations. So, if you have seen those questions or solutions then probably this will also natural come to mind. As I keep saying, it's all about practice.
@@techdose4u I still not understood plz give some examples to prove this statement
How did you come up with the idea for 3rd or 4th solution?
Amazing bro
Thanks
Just concat one array with the reverse of the same array and apply kdanes algo .... Guess it should wordk
Third method: (JAVA)
class Solution {
public int maxSubarraySumCircular(int[] nums) {
int n=nums.length;
int minS=100000;
int maxS=-100000;
int currMaxS=0;
int currMinS=0;
int total=0;
boolean check=false;
boolean allNegative=true;
for(int i=0;i=0) allNegative=false;
// sum of all numbers
total+=nums[i];
// min subarray
if(currMinS>0) currMinS=0;
currMinS+=nums[i];
minS=Math.min(minS,currMinS);
// max subarray
if(currMaxS
Hello Carlos, Could you please help me to understand Sol-2, "Find Max SubArray Sum with Max Window Size-N", I could not understand his approach- How he is moving Left and Right pointers. Thank You in Advance
@@SumitSharma-cq2cf I don't know either.
Can we just find the kadane of 2 concatenation
I don't think so. The max subarray found must also be contiguous.
Hii bro can u please recommends any algorithms books that will more helpful to learn algorithms better..
I tried your alternative method and it worked on first go itself. I tried to understand why it works? and failed to understand the logic. could you please help?
What’s software do you use to record screen and free hand typing
Camtasia + Wacom
Using your method:
Array: [1,-2,3,-2]
Minimum subarray sum=-2
total array sum=0
max subarray sum=0-(-2) = 2
Correct answer = 3 NOT 2
In the last approach, why are we comparing tmp_max and tmp_min to zero?
++
For input array (-5, -3, 2, -4) , the above logic not working. Total array sum will be -10 and min array sum will be -10 and if we subtract them -10-(-10) then it equals 0 .
But max array sum should be 2.
Am I missing anything. Please help
How You came up with this kinda logic like in method 3 and 4?
I knew 3 methods. I took the 4th method from best time solution after submitting. I just dry ran on several examples and I explained the logic what I got.I wanted to discard this from including in the video, but I still included it 😅.This type of algos are not algos but tricks and it won't help during interviews. So I am not a fan of method 4. But method 3 is very common and intuitive. Method 3 is very useful for many problems.
In the 2nd method-- min sub-array sum and total array sum if the input is [5,-3,2,-6,-1,4] the min sub array will be =-7 and total sum will be -1 which is equal to -8, which is wrong. XXXXX.
Could you tell what software you use to write while explaining the concepts. Its really neat and helpful for keeping notes. Great video by the way.
Wacom tablet + software
fantastic
Thanks :)
approach 3 is failing for the test case : -3 -18 -22 -21 -17 16 -14 28 - 22
please check ur final soln with arr = [-10,-7,9,-7,6,9,-9,-4,-8,-5] Expected ans: 17, i guess above algo will return 9
won't it be better to keep a boolean variable initially set false 'onePositiveFound' to indicate at least 1 non-negative value was found in the array and return final ans based upon it?
how is this going to help me learn code and prove that I am a good coder?
genius algorithms
Thank you so much ....
Welcome :)
How is first approach O(n^^2) ? Shouldnt it be O(2n)?
3rd method is failing for the input 1,-2,3,-2
No dude it's working I tried it
Actually this is working with what I explained. NOTE: You need to take max of both cases. I just showed the first case and missed the 2nd case. The 2 cases are max subarray sum in array without wrap and 2nd one is max subarray sum with wrap around. We take max of both to return as answer. You can see that for method 4 I did include both cases while returning and I explained in code as well. In the same way, you need to do for method 3 as well. I just roughly explained it to give the idea.
@@techdose4u
// appliying Kadane's algorithm with inversion method
int max_sum = A[0], vec_sum = 0, inversion_sum = 0, ends_here = 0;
for(int i = 0; i < A.size(); i ++){
// array sum
vec_sum += A[i];
// inversion sum of array
inversion_sum += (A[i]*-1);
// below algo is completely same as Kadane's algorithm
ends_here = ends_here + A[i];
if(ends_here > max_sum)
max_sum = ends_here;
if(ends_here < 0)
ends_here = 0;
}
cout
@@AKASHKUMAR-we5hg Can you explain how. Even I think its not working .
1st method (O(n^2)) solution
#include
#include
using namespace std;
int kadane(int start,int n,int a[]){
int curr_max=a[start];
int global_max=a[start];
start=start+1;
for(int i=1;in-1) {
start=start%n;
}
curr_max=max(a[start],curr_max+a[start]);
global_max=max(global_max,curr_max);
start++;
}
return global_max;
}
int main()
{
int n;
cin>>n;
int a[n];
for(int i=0;i>a[i];
}
int max_circular_subarr_sum=INT_MIN,start;
for(int i=0;i
I think your inverted solution might not work properly for the all postive no.s case so we might also consider it as a special or something???
This one is so hard to implement!!
Ithink it fails here {4,-1,2,6,-1,7,1,-10,5} suppose this array here min subArraySum =-10 and arrSum=5 now it will give maxSubArraySum=15 but the ans in 9 you should take sum of non-contributing elements instead of minSubArraysum. sum of non-contributing elements=-4 arrSum=5 so ans is 9 which is correct.
This algorithm I understood but still confused how this works like Y we're doing all this?
Something new fot me
Great :)
u my dronacharya
I am honoured 😁
what is the difficulty level of this question ??
I tried option 2. Seemed logical. Until I realized there wasn't a clear solution of what to do when the sum gets reset to 0. The left pointer becomes invalid. Oops! Tried to work around the issue, ended up with a mess.
Hello, Could you please help me to understand Sol-2, "Find Max SubArray Sum with Max Window Size-N", I could not understand his approach- How he is moving Left and Right pointers. Thank You in Advance
Bro at 5.56 time your method fails
Input:
N = 9
ar [] = { -3 -18 -22 -21 -17 16 -14 28 -22
}
Its Correct output is:
30
And Your Code's output is:
8
INT_MIN
I dint understand what to write in c++ code
Same
3rd one best
3rd method not working [1, -2, 3, -2] correct ans=3 , by erd method ans=2.
at the end we need to take max of normal kandal algorithem and 3rd method answer.
In method 4, how is the total sum = min sum, if all elements are positive? Can someone please explain this?
Not positive, total_sum = min_sum when all the elements are negative, run a brute force, you'll understand
Is your name Satyam Kumar?
Nope. Follow linkedIn and Instagram to know me 😉
isn't the 3rd and 4th methods exactly same..
SOLUTION:-
int maxSubarraySumCircular(vector& nums) {
int mx=*max_element(nums.begin(),nums.end());
if(mx
your every video lefts many confusions though you dont explain it well
man why dont u show full approaches just because its difficult to implement like what is wrong with u
kya bakwas and boring video bnayi hai.
This person has just horribly messed up the whole solution! If you are showing multiple approaches, please dont pin rudimentary explanation for something not explained in detail
Here is the C++ code of 3rd Method
class Solution {
public:
int maxSubarraySumCircular(vector& A) {
int n=A.size();
int curr_sum=A[0], max_sum=A[0];
for(int i=1;i
Roobot
Poor explanation!!!
In the second solution of min sub-array sum and total array sum if the input is [5,-3,2,-6,-1,4] the min sub array will be =-7 and total sum will be -1 which is equal to -8, which is wrong. XXXXX.