The maximum subarray problem is the task of finding the contiguous subarray within a one-dimensional array, a[1...n], of numbers which has the largest sum, where,

Maximum subarray

Maximum subarray

Example

The list usually contains both positive and negative numbers along with 0. For example, for the array of values −2, 1, −3, 4, −1, 2, 1, −5, 4 the contiguous subarray with the largest sum is 4, −1, 2, 1, with sum 6.

References

Implementations

  • 1

    # TODO: Implement in Python

  • 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

    const D = [-2, -3, 4, -1, -2, 1, 5, -3];

const maxSubarraySum = (function maxSubarray(array) {
  let maxSoFar = 0;
  let maxEndingHere = 0;

  console.log('Initializing maxSoFar = 0 & maxEndingHere = 0');

  for (let i = 0; i < array.length; i++) {

    console.log(`${maxEndingHere} + ${array[i]}`);
    
    maxEndingHere += array[i];
    
    console.log(`=> ${maxEndingHere}`);

    if (maxEndingHere < 0) {
      
      console.log('maxEndingHere is negative, set to 0');
      
      maxEndingHere = 0;
    }

    if (maxSoFar < maxEndingHere) {
      
      console.log(`maxSoFar < maxEndingHere, setting maxSoFar to maxEndingHere (${maxEndingHere})`);
      
      maxSoFar = maxEndingHere;
    }

  }

  return maxSoFar;
}(D));

console.log(`Maximum Subarray's Sum is: ${maxSubarraySum}`);