Maximum Subsequence Sum in Java

Question

I have an array of integers and I want to find the maximum subsequence sum (MSS). I'm trying to solve this problem recursively - using divide and conquer.

The idea is to split the array into half, recurse on the two halves, and then find the maximum sum of the left and right halves of the array, and then compare them with the values I got from recursion.

I know that there are other ways to solve the problem. However, I want to figure out the bug in my code before I look at the other solutions. Right now, with my input, I'm getting the MSS as 12, when it should be 8 (2, 5, -5, 5, 1)

import java.lang.Math;

public class Solution {
  public static void main(String[] args){
    int[] arr = new int[7];    
    arr[0] = 1;
    arr[1] = -3;
    arr[2] = 2;
    arr[3] = 5;
    arr[4] = -5;
    arr[5] = 5;
    arr[6] = 1;
    System.out.println(helper(arr, 0, arr.length - 1));
  }

  public static int helper(int[] arr, int low, int high) {
    if (low >= high) {
        return Math.max(arr[low], 0);
    }

    int mid = low + (high - low) / 2;
    int L = helper(arr, low, mid);
    int R = helper(arr, mid + 1, high);

    int sum = 0;
    int leftSum = 0;

    for (int i = mid - 1; i >= 0; i--) {
        sum = sum + arr[i];
        leftSum = Math.max(leftSum, sum);
    }

    sum = 0;
    int rightSum = 0;

    for (int i = high; i >= mid; i--) {
        sum = sum + arr[i];
        rightSum = Math.max(rightSum, sum);
    }

    return Math.max(L, Math.max(R, leftSum + rightSum));
  }
}

Where exactly am I going wrong?

Edit: I'm trying to find the maximum contiguous sum

The best way to find a bug is... [debugging](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/). — shmosel, Apr 03 '18 at 00:15
But.. the maximum subsequence sum is 13! not 12 or 8 :(. A sub sequence need not be contiguous , a sub array however does! — Srini, Apr 03 '18 at 00:31
@Srini You're right! I'm trying to find the contiguous sub sequence here — MickeyTheMouse, Apr 03 '18 at 01:20
Possible duplicate of [How can I find the maximum sum of a sub-sequence using dynamic programming?](https://stackoverflow.com/questions/8649845/how-can-i-find-the-maximum-sum-of-a-sub-sequence-using-dynamic-programming) — Mad Physicist, Apr 03 '18 at 01:28

score 2 · Answer 1 · answered Apr 03 '18 at 00:43

First of all, I don't see any usage of recursion in your program!
Second, your solution is O(2*n) and is currently wrong!

This solution can be accomplished with O(n) as follows:

import java.lang.Math;

public class Solution {
    public static void main(String[] args){
        int[] arr = {1, -3, 2, 5, -5, 5, 1};
        System.out.println(maximumSubsequenceSum(arr));
    }

    public static int maximumSubsequenceSum(int[] arr) {
        int maxSoFar = 0;
        int maxEndingHere = 0;
        for(int item : arr) {
            maxEndingHere = Math.max(maxEndingHere + item, 0);
            maxSoFar = Math.max(maxSoFar, maxEndingHere);
        }
        return maxSoFar;
    }
}

This solution is purely based on the algorithm described in this paper: Solving the maximum subsequence sum and related problems using BSP/CGM model and multi-GPU CUDA

Yes, I am aware that there is an O(n) solution, and I'm aware of that algorithm. However, that was not what I was asking for. — MickeyTheMouse, Apr 03 '18 at 01:03
O(2n) = O(n). A one pass solution is not necessarily better than a [mulipass](https://m.youtube.com/watch?v=9jWGbvemTag) one. That's just a nitpick though. +1 for fixing all the problems. — Mad Physicist, Apr 03 '18 at 01:26

Maximum Subsequence Sum in Java

1 Answers1