Largest Sum Contiguous Subarray

Largest Sum Contiguous Subarray

- 7 mins

Largest Sum Contiguous Subarray

We are going to have a series of articles on LeetCode problems, everyday a post on a problem on LeetCode. The first post will tacke an Array problem, which is:

Maximum SubArray

Description

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:


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

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. You will probably have experienced solving different competitive programming tasks related to contigous subarrays. Well, I myself when I first encountered the Maximum Sum contigous array challenge in LeetCode, I had no idea that a Kadane's algorithm was existing first of all. I searched on google "maxsubarray leetcode 100% javascript" and one of the result links was:

largest-sum-contiguous-subarray

Found out that there is an Algorithm and it's called Kadan's Algo, using the dynamic programming paradigm to find the Maximum Sub Array.

Below you will find the short cut to the largest sum contiguous subarray solutions.

First, we will solve the problem using the paradigm Dynamic Programming and then we continue using the divide and conquer approach.

The Algorithmic Paradigm is Dynamic Programming and the Time Complexity is O(n)

Dynamic Programming

Dynamic Programming is mainly an optimization over plain recursion. Wherever we see a recursive solution that has repeated calls for same inputs, we can optimize it using Dynamic Programming.

We will write a pseudo code, allowing ourselves to represent the implementation of the algorithm we are going to use, the Kadan’s Algorithm. After the pseudo code, we will continue to add the real code of the algorithm which we will run it in the LeetCode Idle.

Initialize:
  max_so_far = 0
  curr_max = 0

Loop for each element of the array
  (a) max_so_far = array[0]
  (b) curr_max = array[0]

  (c) for each element of the array
          curr_max = max of element and sum of curr_max and element
          max_so_far = max of max_so_far and curr_max
          
return max_so_far

The solution with Dynamic Programming

 

const maxSubArray = (nums) => {
  let max_so_far = nums[0];
  let curr_max = nums[0];

  for (let i = 1; i < nums.length; i++) {
    curr_max = Math.max(nums[i], curr_max + nums[i]);
    max_so_far = Math.max(max_so_far, curr_max);
  }
  return max_so_far;
};

Divide and Conquer Approach

 

var maxSubArray = function (nums) {

  // Return the results of the recursive function
  return findMaxSumInArr(nums);
    
  // Recursive function that will divide and conquer to find the maximum sum from a subarray of the array provided as a parameter
  function findMaxSumInArr(arr) {
    // BASE CASES: 

    // if there is only one arr item, then you can simply return that value
    if (arr.length === 1) {
      return arr[0];
    }
		
    /* 
      if there isn't an arr item, then return -Infinity 
      (we need a valid number for the calculations below. 
      Since JS can only store numbers > -Infinity, -Infinity will never be the max) */
    if (arr.length === 0) {
      return -Infinity;
    }
        
    // Declare zero-indexed length and midpoint
    let length = arr.length - 1;
    let mid = Math.floor(length / 2);
        
    // DIVIDE: Recursively find max sum in the left and right sub arrays
    let lMaxSumInSubArr = findMaxSumInArr(arr.slice(0, mid));
    let rMaxSumInSubArr = findMaxSumInArr(arr.slice(mid + 1, length + 1));
        
    /*
       MERGE: The divide step gave use the max sum on the left and right side,
       but we still need to account for the possibility of a contiguous
       array that goes from left to right through the midpoint
      
    */
		
    // Declare variables to record the maximum contiguous sums for each side
    let lMaxContiguousSum = 0,
      rMaxContiguousSum = 0;
        
    // On the left side, find sum of contiguous array and keep an updated record 
    // of the maximum
    /* 
      (NOTE: in order to account for contiguous arrays that traverse the midpoint,
       start the search from the midpoint - 1 index and traverse leftwards 
       towards index 0. This directionality guarantees that a contiguous array
       traversing the midpoint will be able to add the midpoint itself and the 
       right side's contiguous arr [this is exactly what is checked in the 
       final return statement below]) 
    */
    for (let i = mid - 1, currContiguousSum = 0; i >= 0; i--) {
      currContiguousSum += arr[i];
      lMaxContiguousSum = Math.max(lMaxContiguousSum, currContiguousSum);
    }
       
    // On the left side, find sum of contiguous array and keep an updated 
    // record of the maximum
    /* 
      (NOTE: in accordance with the last note, to account for sub arrays 
      that traverse the midpoint, start the search from the midpoint + 1 
      index and traverse rightwards 
      
    */
    for (let i = mid + 1, currContiguousSum = 0; i <= length; i++) {
      currContiguousSum += arr[i];
      rMaxContiguousSum = Math.max(rMaxContiguousSum, currContiguousSum);
    }
        
    /* 
        RETURN the max sum from the current array: either from the left side,
        right side, or a contiguous sub arrary traversing from left to 
        right through the midpoint 
    */
    return Math.max(
      // The maximum sum from a contiguous subarray that traverses the midpoint
      lMaxContiguousSum + arr[mid] + rMaxContiguousSum,
      // The max sum from each side (whether it was a single value or a contiguous sum) 
      lMaxSumInSubArr,
      rMaxSumInSubArr
    );
  }
};

var nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
console.log(maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]));
Albiona Hoti

Albiona Hoti

comments powered by Disqus
rss facebook twitter github gitlab youtube mail spotify lastfm instagram linkedin google google-plus pinterest medium vimeo stackoverflow reddit quora quora