Kadane’s Algorithm -p2

My Thinking and Approach

In this problem, I was given an array and asked to find the maximum sum of a subarray. At first, I thought of checking all possible subarrays, but that would take too much time.

So I tried to think in an optimized way.

---

Problem Understanding

• We need to find the maximum sum of a contiguous subarray
• The subarray must contain at least one element

---

My Initial Thought

First idea was:

• Generate all subarrays
• Calculate sum for each
• Take the maximum

But this approach takes O(n²) or even O(n³) time, which is not efficient.

So I needed a better approach.

---

Optimized Thinking (Kadane’s Idea)

Instead of checking all subarrays, I thought:

• At every index, I will decide whether to:

  • Continue the current subarray
  • Or start a new subarray

---

My Approach

• Keep a variable currentSum → stores sum of current subarray
• Keep a variable maxSum → stores maximum found so far

Steps:

1. Traverse the array
2. Add current element to currentSum
3. Update maxSum if currentSum is greater
4. If currentSum becomes negative, reset it to 0

---

Code (Java)

```java id="kadane1"
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;
}

}

---

## How I Understood It

* If sum becomes negative → no use carrying it forward
* Start fresh from next element
* Always track the best (maximum) sum

---

## Example Walkthrough

For array:

`[2, 3, -8, 7, -1, 2, 3]`

* Start adding values
* When sum becomes negative at `-8`, reset
* Start again from `7`
* Best subarray becomes `[7, -1, 2, 3]`

Output = `11`

---

## Time and Space Complexity

* Time: O(n)
* Space: O(1)

---

## Understanding from this to me 

From this problem, I learned:

* Not every problem needs brute force
* Sometimes we just need to track values smartly
* Kadane’s Algorithm is very efficient for subarray problems

This improved my thinking towards optimization and helped me understand how to reduce time complexity using simple logic.