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

Maximum Subarray - LeetCode

Solution Link

Maximum Subarray - LeetCode

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

1. Initialise a variable “sum” with 0 to store the sum of contiguous numbers of the array.

2. Initialize a variable maxSum and store value which is the least in every case.

3. Loop through each element of the array

   1. Add the element with the sum of previous numbers.

   2. If sum is greater than the maxSum then update the maxSum value with num.

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

1. Return the indices of the contiguous array.

2. Return the sub-array.

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