> For the complete documentation index, see [llms.txt](https://qatesting.gitbook.io/qa/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://qatesting.gitbook.io/qa/java/data-structures-+-algorithms/sliding-window-technique/leetcode-53.md).

# LeetCode #53

{% embed url="<https://leetcode.com/problems/maximum-subarray/description/>" %}
Given an integer array `nums`, find the subarray with the largest sum, and return *its sum*.
{% endembed %}

<details>

<summary>Understanding Kadane's Algorithm</summary>

### What is the core idea?

Kadane realized that when examining each subarray, we have two choices - either including the current element expands our maximum prefix sum so far, or starting a new prefix from this element. This allows us to track just two values as we iterate through the array.

### Pseudocode

The pseudocode is:

#### Track current/overall maximum prefix:

```java
maxCurrent = first element  
maxOverall = first element
```

#### Iterate through each element:

```java
for i = 1 to length(arr):

  maxCurrent = max(arr[i], maxCurrent + arr[i])

  maxOverall = max(maxCurrent, maxOverall)

```

### Breaking it down:

* Track best prefix so far in maxCurrent
* Compare including/excluding current element
* Update maxOverall after each iteration

We can find the optimal subarray in one linear pass this way!

</details>

#### Track current/overall maximum prefix:

```java
int maxSum = nums[0];
int currentSum = nums[0];
```

#### Iterate through each element:

```java
for(int i=1; i<nums.length; i++) {
    currentSum = Math.max(nums[i], currentSum + arr[i]);
    maxSum = Math.max(currentSum, maxSum)
}
```

From the Math Class:

<div data-full-width="true"><figure><img src="/files/8p4wAGE7MA4YKOTMjkOT" alt=""><figcaption></figcaption></figure></div>

Solution:

> You must understand Kadane's Algorithm to answer this, as you literally copy its format.

```java
class Solution {
    public int maxSubArray(int[] nums) {
        int maxSum = nums[0];
        int currentSum = nums[0];

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

        return maxSum;
    }
}
```