DEV Community

Dev Nirwal
Dev Nirwal

Posted on

Kadane's Algorithm: Leetcode 53 Maximum subarray

Intuition

We can build the intuition based on the two-point approach.

Approach

We will start with two variables maxSum and maxTillNow.

  • The first variable stores the max sum we have attained overall in the array.

  • The second variable stores the value of the maximum sum attained till the current index. Since the array has a negative value, this value will fluctuate, but whenever we get maxSum < maxTillNow, we update the maxSum.

  • The final case we have to handle will be if the maximum sum till any index reaches zero, i.e., maxTillNow < 0, reset the maxTillNow = 0 at the end of loop.

Complexity

  • Time complexity: O(N)

  • Space complexity: O(1)

Code

class Solution {
    public int maxSubArray(int[] nums) {
        int maxSum = Integer.MIN_VALUE;
        int maxTillNow = 0;
        for(int i =0;i<nums.length;i++){
            maxTillNow+=nums[i];
            maxSum = Math.max(maxTillNow,maxSum);
            if(maxTillNow<0) maxTillNow = 0;
        }
        return maxSum;
    }
}
Enter fullscreen mode Exit fullscreen mode

GitHub repo for more solutions: Git
Leetcode profile: Leetcode: devn007

Sentry image

Hands-on debugging session: instrument, monitor, and fix

Join Lazar for a hands-on session where you’ll build it, break it, debug it, and fix it. You’ll set up Sentry, track errors, use Session Replay and Tracing, and leverage some good ol’ AI to find and fix issues fast.

RSVP here →

Top comments (0)

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay