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.
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
I agree, thanks for the clarification. class Solution: def maxSubarraySumCircular(self, nums: List[int]) -> int: # Edge Case: If all are negatves, return the maximum possible negative maximum_possible_negative = -float("inf") all_negatives = True for num in nums: if num < 0: maximum_possible_negative = max(maximum_possible_negative, num) else: all_negatives = False break if all_negatives: return maximum_possible_negative ### EDGE Case Handling Ends # Now, find: # 1. Minimum Subarray Sum (Reversed Kadanes Algo) # 2. Maximum Subarray Sum (Kadanes Algo) # 3. Total Array Sum # 3. The answer is Maximum((TOTAL_ARRAY_SUM - MINIMUM_SUBARRAY_SUM), MAXIMUM_SUBARRAY_SUM) total_array_sum = 0 min_ending_here = 0 min_so_far = nums[0] max_ending_here = 0 max_so_far = nums[0] for num in nums: min_ending_here += num if num < min_ending_here: min_ending_here = num if min_so_far > min_ending_here: min_so_far = min_ending_here max_ending_here += num if num > max_ending_here: max_ending_here = num if max_so_far < max_ending_here: max_so_far = max_ending_here total_array_sum += num return max((total_array_sum-min_so_far), max_so_far)
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
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.
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;
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
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.
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
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
[-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.
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.
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++ :)
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.
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?
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.
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.
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.
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
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
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.
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
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?
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
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
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
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.
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...
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.
It's a typical solution that we know the answer and solution first and then explain the problem
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
I agree, thanks for the clarification.
class Solution:
def maxSubarraySumCircular(self, nums: List[int]) -> int:
# Edge Case: If all are negatves, return the maximum possible negative
maximum_possible_negative = -float("inf")
all_negatives = True
for num in nums:
if num < 0:
maximum_possible_negative = max(maximum_possible_negative, num)
else:
all_negatives = False
break
if all_negatives:
return maximum_possible_negative
### EDGE Case Handling Ends
# Now, find:
# 1. Minimum Subarray Sum (Reversed Kadanes Algo)
# 2. Maximum Subarray Sum (Kadanes Algo)
# 3. Total Array Sum
# 3. The answer is Maximum((TOTAL_ARRAY_SUM - MINIMUM_SUBARRAY_SUM), MAXIMUM_SUBARRAY_SUM)
total_array_sum = 0
min_ending_here = 0
min_so_far = nums[0]
max_ending_here = 0
max_so_far = nums[0]
for num in nums:
min_ending_here += num
if num < min_ending_here:
min_ending_here = num
if min_so_far > min_ending_here:
min_so_far = min_ending_here
max_ending_here += num
if num > max_ending_here:
max_ending_here = num
if max_so_far < max_ending_here:
max_so_far = max_ending_here
total_array_sum += num
return max((total_array_sum-min_so_far), max_so_far)
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
sir third approach will not work for this test case [1,-2,3,-2]
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?
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
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.
It's amazing explanation 👍🤩🙏
amazing ...i learnt 2 new methods today
Nice :)
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?? :)
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.
best explanation of this problem. thank you
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
Your explanation could not be any better
3rd Method
int kadan(vector nums){
int sum=nums[0];
int maxs=nums[0];
int n=nums.size();
for(int i=1;i
👍🏼
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
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?
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
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.
Really interesting solution.
Thanks
Thank u sir,,, great explanation as usual
Welcome :)
Nicely explained 😄
Thanks :)
outstanding explanation ! 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
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.
[-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
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.
Very well explained . Thank you so much !
Welcome :)
Amazing solution thanks
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 :)
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.
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
Can we just find the kadane of 2 concatenation
I don't think so. The max subarray found must also be contiguous.
In the last approach, why are we comparing tmp_max and tmp_min to zero?
++
Just concat one array with the reverse of the same array and apply kdanes algo .... Guess it should wordk
I understood your explanation very well, but what gives the intuition to approach this problem like this. please help me develop such intuition
YOU ARE JUST AMAZING....MY DREAM TO MEET YOU.
Ok meet-up done ✅
Amazing!
Thanks 😊
This one is so hard to implement!!
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
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:)
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
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
Great explanation
Thank you so much ....
Welcome :)
super brooo
genius algorithms
What’s software do you use to record screen and free hand typing
Camtasia + Wacom
1st approach index % N will give us end point? if yes then for(int i=0;i
Amazing bro
Thanks
How did you come up with the idea for 3rd or 4th solution?
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?
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
Done!
u my dronacharya
I am honoured 😁
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.
fantastic
Thanks :)
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 .
How is first approach O(n^^2) ? Shouldnt it be O(2n)?
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
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
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
Something new fot me
Great :)
Hii bro can u please recommends any algorithms books that will more helpful to learn algorithms better..
3rd one best
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.
approach 3 is failing for the test case : -3 -18 -22 -21 -17 16 -14 28 - 22
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
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???
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?
what is the difficulty level of this question ??
This algorithm I understood but still confused how this works like Y we're doing all this?
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
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.
how is this going to help me learn code and prove that I am a good coder?
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
INT_MIN
I dint understand what to write in c++ code
Same
SOLUTION:-
int maxSubarraySumCircular(vector& nums) {
int mx=*max_element(nums.begin(),nums.end());
if(mx
isn't the 3rd and 4th methods exactly same..
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.
Is your name Satyam Kumar?
Nope. Follow linkedIn and Instagram to know me 😉
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
your every video lefts many confusions though you dont explain it well
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
man why dont u show full approaches just because its difficult to implement like what is wrong with u
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
kya bakwas and boring video bnayi hai.
Poor explanation!!!
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.