Kadane’s Algorithm – Java

My Approach to Solving Maximum Subarray Sum

Problem Understanding

I was given an integer array arr[], and the goal is to find the maximum sum of a contiguous subarray (subarray must contain at least one element).

Key Observations

• A subarray is continuous.
• We need the maximum sum, not the subarray itself (though we can track it if needed).
• The array can contain negative numbers, which makes the problem interesting.

---

My Thought Process

At first, I considered the brute-force approach:

• Generate all possible subarrays.
• Calculate their sums.
• Return the maximum.

But this would take O(n²) time, which is inefficient for large inputs.

So I started thinking:

“Can I avoid recomputing sums again and again?”

Then I realized:

• Instead of calculating every subarray separately,
• I can keep a running sum while traversing the array.

---

Key Ideawhich i have

While iterating through the array:

1. Keep adding elements to a variable currentSum.
2. If currentSum becomes negative:

• It is useless for future subarrays.
• So, reset it to 0.
  1. Keep track of the maximum value of currentSum in maxSum.

---

Why Reset When Negative?

If the running sum becomes negative, adding future elements will only make things worse.

Example:

currentSum = -5
next element = 3
→ -5 + 3 = -2 (still worse than just 3)

So it's better to start fresh from the next element.

---

Edge Case Consideration

• If all elements are negative:

  • We should return the maximum element, not 0.
  • That’s why maxSum is initialized as arr[0].

---

Final Approach (Kadane’s Algorithm)

• Traverse the array once.

• Maintain:

  • currentSum
  • maxSum

• Update values as we go.

---

Java Implementation

class Solution {
    int maxSubarraySum(int[] arr) {

        int currentSum = 0;
        int maxSum = arr[0];

        for (int i = 0; i < arr.length; i++) {

            currentSum += arr[i];

            if (currentSum > maxSum) {
                maxSum = currentSum;
            }

            if (currentSum < 0) {
                currentSum = 0;
            }
        }

        return maxSum;
    }
}

---

Example Walkthrough

Input:

arr = [2, 3, -8, 7, -1, 2, 3]

Step-by-step:

• Start accumulating sum.
• Reset when it becomes negative.
• Best subarray found: [7, -1, 2, 3]
• Maximum sum = 11

---

Complexity Analysis

• Time Complexity: O(n)
  (Single pass through the array)

• Space Complexity: O(1)
  (No extra space used)

---

Kadane’s Algorithm works because:

• It avoids unnecessary recalculations.
• It smartly decides when to continue and when to restart.

This problem helped me understand how greedy decisions can lead to an optimal solution.

---

Conclusion

Instead of checking all subarrays, I focused on:

• Maintaining a running sum.
• Resetting when it becomes harmful.
• Tracking the best result continuously.

---