Maximum Sum Subarray

Mark as Completed

Lesson

You are given an array of numbers, and your task is to find the maximum sum subarray. The subarray must be contiguous, meaning it must be in the same order as in the initial array. You cannot move values around or remove them. The subarray should have a positive sum, and you need to find the largest possible sum. Write a function maxSubsequence
that takes in an array of numbers and returns the maximum sum.For example, given the array [-2, 5, 2, -1, 3, -1]
, the maximum sum subarray is [5, 2, -1, 3]
, which has a sum of 9. Therefore, maxSubsequence([-2, 5, 2, -1, 3, -1])
should return 9.

Walkthrough

To solve this problem, we can use the "contains algorithm," which has a time complexity of O(n). We will loop through the array and look for all positive, contiguous subarrays, keeping track of the maximum sum as we go. We start with a current maximum and a maximum so far, both set to 0.

We then iterate over each element in the array and calculate the current maximum by taking the maximum of either 0 or the current maximum plus the current element. We also update the maximum so far by taking the maximum of either the current maximum or the maximum so far. This way, we keep track of the largest sum that we have seen so far.

After iterating over the entire array, we return the maximum so far, which represents the largest possible sum of a subarray.

Here's the code for the maxSubsequence
function:

function maxSubsequence(arr) {
  let currentMax = 0;
  let maxSoFar = 0;
  for (let i = 0; i < arr.length; i++) {
    currentMax = Math.max(0, currentMax + arr[i]);
    maxSoFar = Math.max(currentMax, maxSoFar);
  }
  return maxSoFar;
}

The function first initializes the current maximum and the maximum so far to 0. Then it loops through each element in the array and updates the current maximum and maximum so far. Finally, it returns the maximum so far, which represents the largest possible sum of a subarray.

Big O Complexity Analysis:

The time complexity of the maxSubsequence
function is O(n), where n is the length of the input array. This is because we loop through the array once, and each iteration takes constant time.

The space complexity is O(1), because we only use a fixed amount of memory to store the current maximum and maximum so far. We do not create any new data structures, so the space used by the program is constant.

Previous Lesson Next Lesson