DAY 89 - Kadane's Algorithm
Tags: leetcode, algorithms, beginners, tutorial
Published: 2023-08-31 18:53:46

Hey Folks!. Welcome to day 89 of 100DaysOfCode Challenge. We shall be covering the kadane's algorithm today.

---

## Question: Maximum Subarray
Given an integer array `nums`, find the subarray with the largest sum, and return its sum.

### Examples:

**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.

**Example 3:**


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

**Constraints:**

1 <= nums.length <= 10<sup>5</sup>

-10<sup>4</sup> <= nums[i] <= 10<sup>4</sup>

**Follow up:** _If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle._

---

## Question Breakdown:
_The question is pretty simple. Let's define what it wants:-_

- Subarray

> A subarray is a contiguous non-empty sequence of elements within an array.

- We need to find the largest sum of all the subarrays.

### Intuition:

#### Brute Force Approach:

- In a brute force approach or naïve approach, we can run three loops to find it out.
- We will use the first two for loops to form the subarray and another for loop using a third pointer to find the sum inside that subarray.
- We will then update the maximum sum found accordingly.

#### Code: Brute Force Approach:

```cpp

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int maxi = INT_MIN; //to store our max sum
        int n = nums.size();
        for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            // subarray = arr[i.....j]
            int sum = 0;

            //adding up the sum
            for (int k = i; k <= j; k++) {
                sum += nums[k];
            }

            maxi = max(maxi, sum);
        }
    }

    return maxi;
    }
};


```

This gives us a time limit exceeded error as it is a solution of third-order (cubic) time complexity.

---

#### Better Approach:

- If we check our previous approach carefully, we are adding the next element to the previously calculated sum.
- At a moment we don't need all the elements but the previously calculated sum and the next element to add.
- So if we try to optimize it, we can remove our third for loop and calculate the sum while our j pointer is traversing as it can also accumulate the sum for that subarray.

#### Code:

```cpp

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int maxi = INT_MIN; // maximum sum
        int n = nums.size();
    for (int i = 0; i < n; i++) {
        int sum = 0;
        for (int j = i; j < n; j++) {

            sum += nums[j];

            maxi = max(maxi, sum); // getting the maximum
        }
    }

    return maxi;
}
};


```

**Time Complexity:** O(N<sup>2</sup>), where N = size of the array.
**Reason:** We are using two nested loops, each running approximately N times.

This also gives us a TLE, so we need to find a better approach.

### Optimal Approach Intuition:

- The intuition of Kadane's Algorithm says that if a subarray is contributing a negative sum, it should not be considered further.
- Instead of calculating the actual subarray Kadane's algorithm asks us to move further than negative contributions and count only when the sum is not negative.
- Here, we will traverse the given array with a single loop and while iterating we will add the elements to our sum. If at any point the sum becomes less than 0, we will set the sum as 0 as we are not going to consider any subarray with a negative sum.

#### Approach:

- Initialize two variables sum and maxi to calculate the temporary sum and our final result.
- Traverse the array using a for loop with iterator i to the last index and keep adding our sum to the sum variable.
- If at any point our sum is negative means we should not consider this subarray as a part of our answer otherwise update the maximum
- Return our final result as maxi.

#### Code:

```cpp

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        long long sum = 0;
        long long maxi = LONG_MIN;
        for(int i = 0; i < nums.size(); i++){
            sum += nums[i];

            if(sum > maxi){
                  maxi = sum;
            }

            if(sum < 0){
                sum = 0;
            }
        }
        return maxi;
    }
};


```

---

**BONUS: Printing the subarray:**
_If we want to print the subarray we use the following approach in addition to our optimal approach._

```cpp

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        long long sum = 0;
        long long maxi = LONG_MIN;
        int ansStart = -1;
        int ansEnd = -1;
        int tempStart = 0;
        for(int i = 0; i < nums.size(); i++){

            if(sum == 0) tempStart = i; //means our last subarray contributed negative and we have to start new.

            sum += nums[i];

            if(sum > maxi){
                  maxi = sum;
                  ansStart = tempStart;
                  ansEnd = i;
            }

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

        for(int i = ansStart; i<=ansEnd; i++){
            cout << nums[i] << " ";
        }

        return maxi;
    }
};



```


---

## Complexity Analysis:



|Algorithm | Time Complexity |	Space Complexity|
|----------|-----------------|------------------|
|Binary Search Approach	| O(N<sup>3</sup>) |	O(1)|
|Better Approach:	| O(N<sup>2</sup>) | O(1)|
|Optimal Approach:	| O(N) |	O(1)|