CODEWITHSUNDEEP
javascriptarraysalgorithmcomputer-sciencedivide-and-conquer
Galdino Rosas
Galdino Rosas

Reputation: 11

How to apply Divide and Conquer strategy to maximum sum sub-array problem (JavaScript)

I'm a frontend dev looking into learning some basic CS fundamentals. I've been doing some leetcode and came across the maximum sub array problem.

https://leetcode.com/problems/maximum-subarray/

I'm try to implement a D/C solution after watching a few videos and came up with the following solution. However, this is not turning out the correct response.

For the following input I am supposed to be returning 6 but I keep returning 4 instead.

Input:

[-2,1,-3,4,-1,2,1,-5,4]

Expected:

6

Actual:

4

Solution:

var maxSubArray = function(nums) {
    if (nums.length === 1) {
        return nums[0];
    }
    const mid = Math.ceil(nums.length / 2);
    let LSS = maxSubArray(nums.slice(0, mid));
    let RSS = maxSubArray(nums.slice(mid));
    

    let leftSum = 0;
    let rightSum = 0;
    let sum = 0;

    nums.slice(0, mid).forEach(num => {
        sum += num;
        leftSum = Math.max(sum, leftSum);
    });
    sum = 0;
    nums.slice(mid).forEach(num => {
        sum += num;
        rightSum = Math.max(sum, rightSum);
    });

    return Math.max(RSS, LSS, (leftSum + rightSum));
};

can someone please explain what I am missing in this solution?

Upvotes: 1

Views: 855

Answers (3)

Mehran Rahnama
Mehran Rahnama

Reputation: 11

use Kadane’s algorithm , in my opinion is best way with O(n) :

var maxSequence = function(arr){

  var curr_max = 0, max_so_far = 0;

  for(var i = 0; i < arr.length; i++){  
    curr_max = Math.max(0, curr_max + arr[i]);
    max_so_far = Math.max(curr_max, max_so_far);
  }
  return max_so_far;
}

Upvotes: 1

גלעד ברקן
גלעד ברקן

Reputation: 23955

I believe that since leftSum in your code is accumulating from the left-bound towards the right, it is not forming a best sum that's contiguous in the middle. The solution offered in Emma's answer correctly iterates outward from the middle both to the left and to the right, therefore finding the best sum that "crosses" the middle as one of our options to consider.

Upvotes: 0

Emma
Emma

Reputation: 27723

This is a dynamic programming solution, which'll pass:

var maxSubArray = function(nums) {
    for (let index = 1; index < nums.length; index++) {
        nums[index] = Math.max(nums[index], nums[index] + nums[index - 1]);
    }
    return Math.max.apply(Math, nums);
};

Or:

var maxSubArray = function(nums) {
    for (let index = 1; index < nums.length; index++) {
        nums[index] = Math.max(nums[index], nums[index] + nums[index - 1]);
    }
    return Math.max(...nums);
};

By looking at this Python version, you can see how the algorithm works:

class Solution:
    def maxSubArray(self, nums):
        for index in range(1, len(nums)):
            if nums[index - 1] > 0:
                nums[index] += nums[index - 1]
        return max(nums)

and here is a LeetCode's divide and conquer solution (similar to your method) based on Java, there was no JavaScript snippet in there:

class Solution {
  public int crossSum(int[] nums, int left, int right, int p) {
    if (left == right) return nums[left];

    int leftSubsum = Integer.MIN_VALUE;
    int currSum = 0;
    for(int i = p; i > left - 1; --i) {
      currSum += nums[i];
      leftSubsum = Math.max(leftSubsum, currSum);
    }

    int rightSubsum = Integer.MIN_VALUE;
    currSum = 0;
    for(int i = p + 1; i < right + 1; ++i) {
      currSum += nums[i];
      rightSubsum = Math.max(rightSubsum, currSum);
    }

    return leftSubsum + rightSubsum;
  }

  public int helper(int[] nums, int left, int right) {
    if (left == right) return nums[left];

    int p = (left + right) / 2;

    int leftSum = helper(nums, left, p);
    int rightSum = helper(nums, p + 1, right);
    int crossSum = crossSum(nums, left, right, p);

    return Math.max(Math.max(leftSum, rightSum), crossSum);
  }

  public int maxSubArray(int[] nums) {
    return helper(nums, 0, nums.length - 1);
  }
}

References

Upvotes: 1

Related Questions