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

Postmark Image

Speedy emails, satisfied customers

Are delayed transactional emails costing you user satisfaction? Postmark delivers your emails almost instantly, keeping your customers happy and connected.

Sign up

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

Discover a treasure trove of wisdom within this insightful piece, highly respected in the nurturing DEV Community enviroment. Developers, whether novice or expert, are encouraged to participate and add to our shared knowledge basin.

A simple "thank you" can illuminate someone's day. Express your appreciation in the comments section!

On DEV, sharing ideas smoothens our journey and strengthens our community ties. Learn something useful? Offering a quick thanks to the author is deeply appreciated.

Okay