Maximum Subarray | Kadane's Algorithm | Leetcode 53

Maximum Subarray | Kadane's Algorithm
Leetcode problem number 53
Time Complexity: O(n)
Space Complexity: O(1)
JAVA interview programming playlist:
• Interview Programming ...
#java #interviewquestions #leetcode

[@KarmakillsYou]

Please continue this series. Also, please explain the time and space complexity concepts in this series. It will be helpful for FAANG interview preparation.

[@TechnosageLearning]

Sure ,Will make a video on time and space complexity soon

[@bsv1511]

What should happen if all elements in the array are negative?

[@faizuddin4032]

If all elements are negative then the sum will also be negative number

[@saarza9991]

Bro 1st complete ur 5th standard 😂

[@nitikarajpoot9869]

@@saarza9991 aapke pita ji jadge h nhi n to jadzment ku de rhe ho bhai

[@VaibhavGupta-iu4uf]

@@faizuddin4032 no bro if all elements are negative the sum will be negative but she applied a condition that whenever the sum becomes negative we mark it as zero as we will not count it

[@VaibhavGupta-iu4uf]

@@nitikarajpoot9869 yar itni funny baatein kaise kr leti hain ladkiyan

[@harishm3683]

Waiting for FST 7 & ArthurJones / Mike Menzter's Heavy duty training style master !

[@ez1ogod]

Doesn't work when every element is negative. Bruhhhhh!!!

[@TechnosageLearning]

So here mathematics comes into picture.
For negative number the lagest would be just a single number.
For example if array= [-2,-3,-1]
here largest sum would be -1, because -1 is the only largest number here!!

[@gowthamganesh2974]

but we are setting (sum = 0) if the sum is negative then how it take negative elements??
According the given code :
i=0 where a[0] = -2
sum = -2
maxsum = -2
then sum = 0
i = 1 where a[1] = -3
sum = -3
maxsum = -2
then sum = 0
i = 2 where a[2] = -1
sum = -1
maxsum = -2
sum = 0
So were are getting -2 as maxsum!@@TechnosageLearning

[@Aditya-pm9fb]

Before u set the value of sum to 0 u check in the if condition whether the sum > max_sum or not that's where the max_sum gets updated to -1 coz at the end u return max_sum only.@@gowthamganesh2974

[@Aditya-pm9fb]

Before u update the sum variable u check if sum > max_sum thats where the variable gets updated.@@gowthamganesh2974

[@eUREKAA11]

​@@gowthamganesh2974 you are wrong here. At i = 2, Max sum will be -1 because ( -1 > -2) hence maxSum = -1

[@Omkar-fg4ws]

xavier