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 :)

@sureshgarg920

4 жыл бұрын

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 :)

@LegitGamer2345

3 жыл бұрын

@@sureshgarg920 thank u boi

@harshithmundada5100

8 ай бұрын

Won't the third method fail for [-1,-2,-3]

@nitinvadadoriya8280

8 ай бұрын

@@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!

@techdose4u

3 жыл бұрын

Welcome :)

sir third approach will not work for this test case [1,-2,3,-2]

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

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

It's a typical solution that we know the answer and solution first and then explain the problem

Here i am struggling with thinking single solution, and u came up with 4 solutions 😑😑how ur brain works.

@techdose4u

4 жыл бұрын

All are kadane's based only 😅

@sahilkumarsingh2531

10 ай бұрын

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.

@techdose4u

4 жыл бұрын

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.

@KoushikChowdhury2016

4 жыл бұрын

@@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

@evgeni-nabokov

4 жыл бұрын

@@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.

How did you come up with the idea for 3rd or 4th solution?

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

@techdose4u

4 жыл бұрын

Thanks :)

@abdulbasith7911

4 жыл бұрын

Could you share with your prefix array solution.please?

How do you got to the observation that we need to take a difference of total sum with min-sum subarray?

@techdose4u

4 жыл бұрын

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.

@tusharchaturvedi100

3 жыл бұрын

@@techdose4u I still not understood plz give some examples to prove this statement

What’s software do you use to record screen and free hand typing

@techdose4u

4 жыл бұрын

Camtasia + Wacom

really nice. I liked that changing sign solution. You are great, you came up with these many solutions.

@techdose4u

4 жыл бұрын

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.

@rayanahmed1122

4 жыл бұрын

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.

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!

@bruteforceman2311

2 жыл бұрын

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.

outstanding explanation ! Thank you !

Very well explained . Thank you so much !

@techdose4u

4 жыл бұрын

Welcome :)

It's amazing explanation 👍🤩🙏

what is the idea behind method 3? plzz explain ur thought process

@techdose4u

4 жыл бұрын

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 :)

@kollivenkatamadhukar5059

3 жыл бұрын

@@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.

@kollivenkatamadhukar5059

3 жыл бұрын

you must correct Max sum subarray with max sum circular subbaray

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?

best explanation of this problem. thank you

I actually tried to do the 2nd approach. we have to make sure that we dont process the same element twice.

@techdose4u

4 жыл бұрын

I also applied the 2nd approach initially 😅

@yashgoswami5374

Жыл бұрын

@@techdose4u later you found soln on GFG?

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?

@techdose4u

4 жыл бұрын

Thanks. Please read the pinned COMMENT by me. You will get your answer :)

@SinghFlex

4 жыл бұрын

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

@HimanshuSharma-tm2ms

4 жыл бұрын

@@SinghFlex thanks for the clear explanation !! there's a mistake thought (sum-invert val)=8-(-1)=9 should be the correct thing.

@raisanjeeb42

2 жыл бұрын

@@SinghFlex Dude...What an explanation 🙌🙌Thanks

I understood your explanation very well, but what gives the intuition to approach this problem like this. please help me develop such intuition

1st approach index % N will give us end point? if yes then for(int i=0;i

Hii bro can u please recommends any algorithms books that will more helpful to learn algorithms better..

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.

@techdose4u

4 жыл бұрын

Yea

Thank u sir,,, great explanation as usual

@techdose4u

3 жыл бұрын

Welcome :)

amazing ...i learnt 2 new methods today

@techdose4u

3 жыл бұрын

Nice :)

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

The third method doesn't work for [-3,5,6,-1,4,-2]?

@techdose4u

4 жыл бұрын

Which method? The 3rd? You need to take max(inversion_answer,kadane's answer)

@wenyangzhang7605

4 жыл бұрын

Ahh I got it. Thank you so much!

@techdose4u

4 жыл бұрын

Welcome :)

In the last approach, why are we comparing tmp_max and tmp_min to zero?

@trevorPhillips284

2 жыл бұрын

++

How You came up with this kinda logic like in method 3 and 4?

@techdose4u

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.

Great explanation

How is first approach O(n^^2) ? Shouldnt it be O(2n)?

amazing explanation...can you please tell why we need to take max(max_Straight_sum, total_sum - min_straight_Sum) ?

@trevorPhillips284

2 жыл бұрын

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

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.

@rahulagarwal3611

2 жыл бұрын

return max(maxssum,arsum-minssum); you can return this instead to get correct answer

@SumitSharma-cq2cf

2 жыл бұрын

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

@rajaganji7982

2 жыл бұрын

@@SumitSharma-cq2cf It's a sliding window technique. It is a very famous technique. Just google it.

@SumitSharma-cq2cf

2 жыл бұрын

@@rajaganji7982 Sure Thank You I will check this

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???

In your alternative method I guess you forgot to tell one thing if. Temp_maxsum

@techdose4u

4 жыл бұрын

Maybe 😅 Is it present in code?

@yashgupta3127

4 жыл бұрын

@@techdose4u ohh my bad you are making tempsum=0 if sum negetive that will do the trick.sorry.

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++ :)

@techdose4u

4 жыл бұрын

I think some people have already done it. So have a look at their code. You might understand your mistake.

@srividhyaparthasarathy5401

4 жыл бұрын

@@techdose4u thank u so much sir ...u r really too patient to answer all of ur students..hats off:)

Can we just find the kadane of 2 concatenation

@techdose4u

3 жыл бұрын

I don't think so. The max subarray found must also be contiguous.

we have to compare normal kadane answer with the inverted kadane and return maximum of them

@techdose4u

4 жыл бұрын

Yes correct. This is true for method 3 and 4.

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)); }

@techdose4u

4 жыл бұрын

Thanks for sharing

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] int largestElement = nums[0]; for(int i=1;i

Your explanation could not be any better

Thanks for great effort. Something that is missing is WHY any of these methods are "correct".

@SumitSharma-cq2cf

2 жыл бұрын

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 solution thanks

In method 4, how is the total sum = min sum, if all elements are positive? Can someone please explain this?

@eyeamkd

Жыл бұрын

Not positive, total_sum = min_sum when all the elements are negative, run a brute force, you'll understand

Really interesting solution.

@techdose4u

2 жыл бұрын

Thanks

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.

@techdose4u

4 жыл бұрын

Wacom tablet + software

Thank you so much ....

@techdose4u

4 жыл бұрын

Welcome :)

Just concat one array with the reverse of the same array and apply kdanes algo .... Guess it should wordk

super brooo

[-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.

@eyeamkd

Жыл бұрын

irrespective of whether all elements are negative, returning the max_sum value if the condition min_straight_sum == total_sum true works

Amazing bro

@techdose4u

3 жыл бұрын

Thanks

how is this going to help me learn code and prove that I am a good coder?

This one is so hard to implement!!

Nicely explained 😄

@techdose4u

Жыл бұрын

Thanks :)

YOU ARE JUST AMAZING....MY DREAM TO MEET YOU.

@devendrabhuarya4917

Жыл бұрын

Ok meet-up done ✅

This algorithm I understood but still confused how this works like Y we're doing all this?

Amazing!

@techdose4u

2 жыл бұрын

Thanks 😊

what is the difficulty level of this question ??

Done!

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).

@techdose4u

4 жыл бұрын

Yes correct. This is shown in the code for method 4

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?

3rd method is failing for the input 1,-2,3,-2

@AKASHKUMAR-we5hg

4 жыл бұрын

No dude it's working I tried it

@techdose4u

4 жыл бұрын

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.

@AnkitKumarCoder

4 жыл бұрын

@@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 // 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 ends_here = 0; } cout

@siddharthkela1818

4 жыл бұрын

@@AKASHKUMAR-we5hg Can you explain how. Even I think its not working .

fantastic

@techdose4u

3 жыл бұрын

Thanks :)

u my dronacharya

@techdose4u

4 жыл бұрын

I am honoured 😁

INT_MIN I dint understand what to write in c++ code

@techdose4u

3 жыл бұрын

Same

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.

3rd Method int kadan(vector nums){ int sum=nums[0]; int maxs=nums[0]; int n=nums.size(); for(int i=1;i

@techdose4u

3 жыл бұрын

👍🏼

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.

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.

3rd method not working [1, -2, 3, -2] correct ans=3 , by erd method ans=2.

@shekharkumarsingh370

Жыл бұрын

at the end we need to take max of normal kandal algorithem and 3rd method answer.

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

@SumitSharma-cq2cf

2 жыл бұрын

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

@carloscruzado4775

2 жыл бұрын

@@SumitSharma-cq2cf I don't know either.

genius algorithms

approach 3 is failing for the test case : -3 -18 -22 -21 -17 16 -14 28 - 22

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 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.

@SumitSharma-cq2cf

2 жыл бұрын

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

Something new fot me

@techdose4u

3 жыл бұрын

Great :)

isn't the 3rd and 4th methods exactly same..

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

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.

3rd one best

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?? :)

Is your name Satyam Kumar?

@techdose4u

3 жыл бұрын

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

Roobot

SOLUTION:- int maxSubarraySumCircular(vector& nums) { int mx=*max_element(nums.begin(),nums.end()); if(mx

kya bakwas and boring video bnayi hai.

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