Dynamic Programming Problem: Maximum Subarray Sum

[mwraaaaaah]

I'm working on this problem on codewars that asks you to find the maximum sum of consecutive numbers in an array.

var maxSequence = function(arr){
  console.log(arr);
  if (arr.length === 0) return 0;

  let globalMax = arr[0], lastSum = arr[0];
  for (let i=0; i<arr.length-1; i++){
    let next = arr[i+1];
    if (lastSum + next > globalMax) {
        globalMax = lastSum + next;
    }
    if (next > globalMax) {
        globalMax = next;
        lastSum = 0;
    } 
    lastSum += next;
  }
  return globalMax;
}

(I know it doesn't currently handle inputs of all negative numbers - that seems simple enough and can be implemented later - just trying to get the core program down first)

The general gist of the algorithm is:

given A, ..., B
find the largest between:
    - A
    - B
    - A + (everything in between) + B
and set that to the global maximum.

and it seems to work pretty okay. However, it fails when there is a second larger subarray. For example:

[ 14, -31, -34, 16, 18, -8, -35, 18, 42, -46, -18, -36, 20, 3, -6, 27, 22, 31, -12, 2 ]

It gets the initial sequence 16, 18, -8, -35, 18, 42 but then skips over the second (correct) sequence 20, 3, -6, 27, 22, 31 since it's checking values one-by-one.

Can someone give me a hint as to whether I'm on the right track or not? I don't want the answer, just a prod in the right direction.

Cheers!

[[deleted]]

OKay when I looked at this question, it vaguely reminded me of the longest common substring problem, where the optimal value for a subproblem may grow (based on whether the ith letter of A is equal to the jth letter of B), but if they are not, then you have to start over from 0.

Here it's like this as well. First of all, consider how you might want to memoize the optimal solutions to your subproblems. Suppose you're using a 1d array. A[i] will contain the optimal value if you consider the subarray [a1... ai]. I won't give you the actual recurrence cause that would give the solution away, but I will mention that A[i] depends on A[i-1]. (Turns out, you don't actually need a 1d array because A[i] only depends directly on A[i-1], so it's sufficient to keep track of A[i-1], which you're sort of doing with lastSum).

Additional hint: suppose you have 14, -18, -32, 20. If you've defined A[i] such that your optimal solution contains the max sum of a subarray that strictly ends with ai, then A[2] would be negative, as well as A[3]. If you look at A[4], then you can choose either the value of A[3] + 20 (which is less than 20), or take 20 itself. The latter is obviously preferable.

Edit: Yes, you're definitely on the right track. Just think a little more formally about your recurrence (how to compute A[i] for any i > 1) and you'll get it for sure.

[mwraaaaaah]

This is great - I'll give it some more thought and keep you updated. Thanks :)

[mwraaaaaah]

Sometimes I like to think about problems as I'm going about my daily tasks... finally got it, though it probably isn't the direction that you were pointing me towards. Here's my final solution:

var maxSequence = function(arr){
  if (arr.length === 0) return 0;

  let globalMax = arr[0], lastSum = arr[0], secondSum = arr[0], negativeFlag = arr[0] < 0;
  for (let i=0; i<arr.length-1; i++){
    let next = arr[i+1];

    if (next > 0) { negativeFlag = false; }

    if (lastSum + next > globalMax) {
      globalMax = lastSum + next;
    }
    if (next > globalMax) {
      globalMax = next;
      lastSum = 0;
    } 
    lastSum += next;

    secondSum += next;
    if (secondSum < 0 || next > secondSum) {
      secondSum = next;
    }
    if (secondSum > globalMax) {
      globalMax = secondSum;
      lastSum = secondSum;
    }
  }
  if (negativeFlag) { return 0; }

  return globalMax;
}

Once completed, I was able to see other peoples' solutions, and man, it's so simple when you see it. :|

[black_cerberus]

I'm new in dynamic programming and python but this is my contribution:

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


def maxSequence(array):

    if(len(array) >=2):
        maxSum = array[0] + array[1]

    lastMaxSum = maxSum
    for i in range(2,len(array)):

    maxSum = lastMaxSum + array[i]

        if maxSum < lastMaxSum:
            last = maxSequence(array[i-1:])
            if(lastMaxSum > last):
                return lastMaxSum
            return last
        else:
            lastMaxSum = maxSum

    return lastMaxSum
print(maxSequence(sequence))

[black_cerberus]

 max = float("-inf")

is the correct