1. Problem statement

Given an integer array nums, find the subarray with the largest sum, and return its sum.

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum 6.

Example 2:

Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum 1.

2. Core Idea of Kadane’s Algorithm

At every element in the array, we decide:

• Should we extend the previous subarray by adding this element?
• Or should we start a new subarray beginning at this element?
• At each step, ask: “Would it be better to start over from here or continue?”
• If your current sum becomes worse than starting fresh, reset it.

We keep track of two variables:

• currentMax: Maximum subarray sum ending at current index.
• maxSoFar: Maximum sum found so far at any point.

At each step:

currentMax = max(currentElement, currentMax + currentElement)
maxSoFar = max(maxSoFar, currentMax)

This allows you to skip over “bad” parts of the array and start from a more promising point.

3. Step-by-Step Walkthrough with Table

Let’s go through nums = [-2,1,-3,4,-1,2,1,-5,4] step by step.

Index (i)	Element (nums[i])	currentMax	maxSoFar	Explanation
0	-2	-2	-2	Start with first element
1	1	max(1, -2+1) = 1	1	Better to start fresh
2	-3	max(-3, 1+(-3)) = -2	1	Add -3 lowers sum, so start fresh
3	4	max(4, -2+4) = 4	4	Start new from 4
4	-1	max(-1, 4+(-1)) = 3	4	Continue from 4
5	2	max(2, 3+2) = 5	5	Continue
6	1	max(1, 5+1) = 6	6	Continue
7	-5	max(-5, 6+(-5)) = 1	6	Continue (sum decreases)
8	4	max(4, 1+4) = 5	6	Continue

4. Java solution

public class MaximumSubarray {
    public int maxSubArray(int[] nums) {
        int currentMax = nums[0];
        int maxSoFar = nums[0];

        for (int i = 1; i < nums.length; i++) {
            currentMax = Math.max(nums[i], currentMax + nums[i]);
            maxSoFar = Math.max(maxSoFar, currentMax);
        }

        return maxSoFar;
    }
}