# 53. Maximum Subarray Sum / Kadane

## Problem Statement

\
Given an integer array `nums`, find the 

subarray with the largest sum, and return *its sum*.

 

**Example 1:**

<pre><code><strong>Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
</strong><strong>Output: 6
</strong><strong>Explanation: The subarray [4,-1,2,1] has the largest sum 6.
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: nums = [1]
</strong><strong>Output: 1
</strong><strong>Explanation: The subarray [1] has the largest sum 1.
</strong></code></pre>

**Example 3:**

<pre><code><strong>Input: nums = [5,4,-1,7,8]
</strong><strong>Output: 23
</strong><strong>Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.
</strong></code></pre>

&#x20;

**Constraints:**

* `1 <= nums.length <= 105`
* `-104 <= nums[i] <= 104`

&#x20;

## Intuition

```
"Very efficient solution to find maximum subarray sum
        
Intuition- negative nos are not carried forward in the sum  
only positive are carried forward
"
```

### Links

<https://leetcode.com/problems/maximum-subarray/>

### Video Links

<https://www.youtube.com/watch?v=w_KEocd__20&list=PLgUwDviBIf0rPG3Ictpu74YWBQ1CaBkm2&index=6>

### Approach 1:

```
Kadane Algorithm
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int sum=0;
        int maxi=nums[0];
        int n=nums.size();

        for(int i=0;i<n;i++){
            sum+=nums[i];

            if(sum>maxi)
                maxi=sum;
            // We dont want to carry forward the negative sum as it will lead to
            // neg sum as we go
            if(sum<0)
                sum=0;
        }

        return maxi;
    }
};
```

{% endcode %}

### Approach 2:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###