Striver's SDE Sheet Journey - #4 Kadane's Algorithm
Tags: beginners, programming, java, computerscience
Published: 2021-12-21 11:13:17

Hi👋Devs,

In the previous post, we have solved and understood the [**_Next Permutation_**](https://dev.to/sachin26/strivers-sde-sheet-journey-3-next-permutation-14gp) problem and in this post, we will tackle the next one **Kadane’s algorithms**.


## #4 Kadane's Algorithms

_in this problem we have given an integer array `nums`, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum._

> Example 1:

**Input**: `nums` = [-2,1,-3,<u>**4,-1,2,1**</u>,-5,4]
**Output**: `6`
_Explanation_: [4,-1,2,1] has the largest sum = 6.


> Example 2:

**Input**: `nums` = [<u>**1**</u>]
**Output**: `1`


## <u>Solution</u>

we can easily solve this problem by using the kadane's algorithms.
lets discuss the Kadane's algorithms step by step.


**step-1** initialize three int variable `sum = 0` ,`max = nums[0]`, `arrSize = nums.length`. 

**step-2** run a loop from `i = 0` to `arrSize`.
> **1.** sum = sum + nums[i].
> **2.** if `sum > max` then `max = sum`.
> **3.** if `sum < 0` then `sum = 0`.

**step-3** return `max`

**step-4** end

**why reinitialize `sum = 0` if `sum < 0`?**
_negative-sum never contribute to maximum sum, so it is better to reinitialize sum to 0 and start adding from next element_

before coding this algorithm in java, have a look at this image for a better understanding of this algo.

<img src="https://dev-to-uploads.s3.amazonaws.com/uploads/articles/0bdfx5uj6egi3cpb9lmp.png" alt="kadane's algo" width="500" height="900" />


> _Java_

```java
class Solution {
    public int maxSubArray(int[] nums) {
        int sum = 0;
        int max = nums[0];
        int arrSize = nums.length;
        
        for(int i=0; i < arrSize; i++){
            sum = sum + nums[i];
            
            if(sum > max){
                max = sum;
            }

            if(sum < 0) {
                sum =0
            }
        }
        
        return max;
        
}
}
```

**But how? can we know,**

- length of the max subarray

- start & end index of the max subarray

- elements of the max subarray

so, for these, we can make two more int variables `firstIndex` & `lastIndex` that store the start & last index number of the max subarray and then do some modification in the **step-2**.

> **step-2** run a loop from `i = 0` to `arrSize`.
> > **1.** sum = sum + nums[i].
> > **2.** if `sum > max` then `max = sum`,**`lastIndex = i`**.
> > **3.** if `sum < 0` then `sum = 0`, **`firstIndex = i+1`**.

by using `firstIndex` and `lastIndex` variables, now we can answer the following questions.

- **length of the subarray**. 
`subArrSize = lastIndex - firstIndex`

- **start & end index of subarray**.
by using `firstIndex` and `lastIndex` variable

- **elements of the max subarray**.
by traversing from `firstIndex` to `lastIndex` we can find the elements


> _Java_

```java
class Solution {
    public int maxSubArray(int[] nums) {
        int sum = 0;
        int max = nums[0];
        int arrSize = nums.length;
        int firstIndex = 0,lastIndex = 0;
        
        for(int i=0; i < arrSize; i++){
            sum = sum + nums[i];
            
            if(sum > max){
                max = sum;
                lastIndex = i;
            }
            if(sum < 0) {
                sum =0;
                firstIndex = i + 1;
            }
        }
        
        return max;
        
}
}
```
---

> **_Time Complexity⏱️_**

running a for loop from 0 to arrSize.
so, **O(arrSize)** will be it's time complexity.




> **_Space Complexity⛰️_**

the algo is not using any extra space, then **O(1)** will be its space complexity. 


if you like this article please let me know in the comment section.
if you find anything wrong in the post,plz correct me.
Thank you for reading my article.