# Problem

## Statement

Given an integer array `nums`

, find the contiguous subarray (containing at least one number) which has the largest sum and return *its sum*.

A **subarray** is a **contiguous** part of an array.

**Example 1:**

```
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
```

**Example 2:**

```
Input: nums = [1]
Output: 1
```

**Example 3:**

```
Input: nums = [5,4,-1,7,8]
Output: 23
```

**Constraints:**

`1 <= nums.length <= 105`

`104 <= nums[i] <= 104`

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

## Link

# Solution Link

# Explanation

## Approach

**Kandane’s algorithm**

A) Lets’ consider taking a number that would always be the least number in the entire number system. This is because I want to make sure my first max number is greater than this least number.

B) Let’s take a number to store the sum of the elements traversed in the array.

### Algorithm

- Initialise a variable “sum” with 0 to store the sum of contiguous numbers of the array.
- Initialize a variable maxSum and store value which is the least in every case.
Loop through each element of the array

- Add the element with the sum of previous numbers.
- If sum is greater than the maxSum then update the maxSum value with num.
Also check if the sum is less than 0 set it to 0 again.

**Now why is this required?**There’s no point in storing a number less than 0 because we only have to check the greatest number among the negative numbers because if we keep adding negative numbers it becomes the opposite of greatest number.

## JavaScript Code Implementation

```
/**
* @param {number[]} nums
* @return {number}
*/
var maxSubArray = function(a) {
let maxSum = -(Math.pow(2, 53) - 1); // A
let sum = 0;
for(let i = 0; i< a.length; i++) {
sum += a[i];
if(sum > maxSum) {
maxSum = sum;
}
if(sum < 0) {
sum = 0;
}
}
return maxSum;
};
```

Now I urge you to read the code and do a dry run in your mind to understand it fully.

## Conclusion

You have to keep practising these three variant of this problem to fully understand this and explain this in a real interview

- Return the indices of the contiguous array.
- Return the sub-array.

If you like the content do drop me follow on Twitter learn these concepts with easy.

### Did you find this article valuable?

Support **Sagar Sengupta** by becoming a sponsor. Any amount is appreciated!