7

I am trying to find the contiguous subarray within an array which has the largest sum. So, for the array

{5, 15, -30, 10, -5, 40, 10}

the maximum sum possible using those numbers contiguously would be 55, or (10 + (-5) + 40 + 10) = 55. The program below outputs the maximum sum of 55, however, the problem I am trying to figure out is how to print the sequence that produces this 55. In other words, how can I print out the 10, -5, 40, and 10?

public static void main(String[] args) {
    int[] arr = {5, 15, -30, 10, -5, 40, 10};

    System.out.println(maxSubsequenceSum(arr));         
}

public static int maxSubsequenceSum(int[] X) {
    int max = X[0];
    int sum = X[0];

    for (int i = 1; i < X.length; i++) {
        sum = Math.max(X[i], sum + X[i]);
        max = Math.max(max, sum);
    }
    return max;
}

I was thinking of creating an ArrayList to store the sum values at every index of i, so the ArrayList would look like (5, 20, -10, 10, 5, 45, 55). And then I was planning on clearing the ArrayList from index 0 to the first negative number in the list, however, this only solves the problem for this specific example, but if I change the original array of numbers, this solution won't work.

Improve this question

8 Answers 8

Reset to default
5

You can replace Math.Max functions by if statements and update start and end index of the best subarray. Pascal version:

    if X[i] > sum + X[i] then begin
        sum := X[i];
        start := i;
      end
      else
        sum := sum + X[i];
      if max < sum then begin
        max := sum;
        finish := i;
      end;
Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Your solution is even better than mine ... I hadnt noticed I could optimize away some useless tracking on the indexes. Well done :)
3

You can track the starting and ending indexes of the current best subarray in your loop. Instead of using max() to compute sumand max, just do the following :

int sum_start = 0, sum_end = 0, start = 0, end = 0;
// In the for loop
if (X[i] > sum + X[i]) {
    sum = X[i];
    sum_start = i;
    sum_end = i;
} else {
    ++sum_end;
}
if (sum > max) {
    start = sum_start;
    end = sum_end;
    max = sum;
}
Improve this answer

Comments

2

there is an o(n) solution, a single for loop through the array and reset your sub-sequence whenever your current total is below 0.

{5, 15, -30, 10, -5, 40, 10}

  • 5 + 15 = 20
  • 20 - 30 = -10 (reset sub-sequence)
  • 10 -5 +40 +10 = 55
  • end. 55 is max sub-sequence

edit: to get subsequence... whenever you change max, update your subsequence

  • current left index changes only when u reset
  • current right index changes every iteration
  • new max -> save current left and right index...
Improve this answer

1 Comment

The problem is asking for the subsequence itself, not just its sum.
0

It can be done by capturing the start and end while identifying maximum sub-array as follows:

Code

package recursion;

import java.util.Arrays;

public class MaximumSubArray {

    private static SubArray maxSubArray(int[] values, int low, int high) {
        if (low == high) {
            // base condition
            return new SubArray(low, high, values[low]);
        } else {
            int mid = (int) (low + high) / 2;
            // Check left side
            SubArray leftSubArray = maxSubArray(values, low, mid);
            // Check right side
            SubArray rightSubArray = maxSubArray(values, mid + 1, high);
            // Check from middle
            SubArray crossSubArray = maxCrossSubArray(values, low, mid, high);
            // Compare left, right and middle arrays to find maximum sub-array
            if (leftSubArray.getSum() >= rightSubArray.getSum()
                    && leftSubArray.getSum() >= crossSubArray.getSum()) {
                return leftSubArray;
            } else if (rightSubArray.getSum() >= leftSubArray.getSum()
                    && rightSubArray.getSum() >= crossSubArray.getSum()) {
                return rightSubArray;
            } else {
                return crossSubArray;
            }
        }
    }

    private static SubArray maxCrossSubArray(int[] values, int low, int mid,
            int high) {
        int sum = 0;
        int maxLeft = low;
        int maxRight = high;

        int leftSum = Integer.MIN_VALUE;
        for (int i = mid; i >= low; i--) {
            sum = sum + values[i];
            if (sum > leftSum) {
                leftSum = sum;
                maxLeft = i;
            }
        }

        sum = 0;
        int rightSum = Integer.MIN_VALUE;
        for (int j = mid + 1; j <= high; j++) {
            sum = sum + values[j];
            if (sum > rightSum) {
                rightSum = sum;
                maxRight = j;
            }
        }
        SubArray max = new SubArray(maxLeft, maxRight, (leftSum + rightSum));
        return max;
    }

    static class SubArray {

        private int start;

        private int end;

        private int sum;

        public SubArray(int start, int end, int sum) {
            super();
            this.start = start;
            this.end = end;
            this.sum = sum;
        }

        public int getStart() { return start; }

        public void setStart(int start) { this.start = start; }

        public int getEnd() { return end; }

        public void setEnd(int end) { this.end = end; }

        public int getSum() { return sum; }

        public void setSum(int sum) { this.sum = sum; }

        @Override
        public String toString() {
            return "SubArray [start=" + start + ", end=" + end + ", sum=" + sum + "]";
        }
    }

    public static final void main(String[] args) {
        int[] values = { 5, 15, -30, 10, -5, 40, 10 };
        System.out.println("Maximum sub-array for array"
            + Arrays.toString(values) + ": " + maxSubArray(values, 0, 6));
    }

}

Output

Maximum sub-array for array[5, 15, -30, 10, -5, 40, 10]: SubArray [start=3, end=6, sum=55]

Solution can be downloaded from https://github.com/gosaliajigar/Programs/blob/master/src/recursion/MaximumSubArray.java

Improve this answer

Comments

0

Two subarray are

[1, 2, 3]

and [4, 9] excluding the negative number

The max sub array here is [ 4, 5]

so the output is 9

Here is the code

public class MaxSubArray{
static void sumM(int a[], int n){
    int s1 = Integer.MAX_VALUE;
    int k = Integer.MAX_VALUE;
    int sum = 0;
    int s2 = 0;
    for(int i=0;i<n;i++){

        if(a[i]<s1){
            if(a[i]<0){
                k = Math.min(a[i],s1);
            }
        }

        if(a[i]>k){
            sum+=a[i];
        }

        if(a[i]<k){
            if(a[i]<0){
                continue;
                
            }
            s2+=a[i];
        }

    }
        if(sum>s2){
            System.out.println(sum);
        }
        else{
            System.out.println(s2);
        }
    
     
}

    public static void main(String[] args){
        int a[] = {1,2,3,-7,4,5};

        int n = a.length;

        sumM(a,n);
    }

    
}
Improve this answer

Comments

0 
 public static int kadane(int[] A) {
        
    int maxSoFar = 0;
 
        
    int maxEndingHere = 0;
 
    // traverse the given array
    for (int i: A) {
         // update the maximum sum of subarray "ending" at index `i` (by adding the
         // current element to maximum sum ending at previous index `i-1`)
         maxEndingHere = maxEndingHere + i;
 
         // if the maximum sum is negative, set it to 0 (which represents
         // an empty subarray)
         maxEndingHere = Integer.max(maxEndingHere, 0);
 
         // update the result if the current subarray sum is found to be greater
         maxSoFar = Integer.max(maxSoFar, maxEndingHere);
     }
 
     return maxSoFar;
}
Improve this answer

Comments

0 

var maxSequence = function(arr){
  // ...
  if (arr.every((ele) => ele >= 0)) {
    return arr.reduce((sum, ele) => sum + ele, 0);
  } else if (arr.every((ele) => ele < 0)) {
    return 0; 
//for me the maximum would be the biggest negative number 
//arr.reduce((max, elm) => (max > elm ? max : elm))
  } else if (arr === [0]) {
    return 0;
  } else {
    let maxSum = [];
    let currentSum = 0;
    for (let i = 0; i < arr.length; i++) {
      currentSum = Math.max(arr[i], currentSum + arr[i]);
      maxSum.push(currentSum);
    }
    return maxSum.reduce((max, elm) => (max > elm ? max : elm));
  }
}

Improve this answer

1 Comment

Your answer could be improved with additional supporting information. Please edit to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center.
-3

you need to sum all possible sub array. to do that, you can do this code

public static int maxSubsequenceSum(int[] X) {
    int max = 0;
    boolean max_init = false;
    int max_from=0;
    int max_to=0; // this is not included
    for (int i = 0; i < X.length; i++) {
        for (int j = i + 1; j < X.length + 1; j++) {
            int total = 0;
            for (int k = i; k < j; k++) {
                total += X[k];
            }
            if (total > max || !max_init){
                max = total;
                max_init = true;
                max_from = i;
                max_to = j;
           }
        }
    }
    for (int i=max_from;i<max_to;i++)
       System.out.print(X[i]+",");
    System.out.println();
    return max;
}
Improve this answer

8 Comments

Surely there's a more efficient solution, though?
This seems a little inefficient. I am trying to maintain linear time.
you have to find (N * (N + 1))/2 sum. because you have this amount posible sum. over my solution, some total might be used for next turn as a optimization. but still, you have to have a loop with (N * (N + 1))/2 turn. this is 2 outer loops in my solution
@Adem Ah, I see. Where in this solution can I print or store the actual sequence of numbers that produces max?
@Adem You don't need to find all (N * (N + 1))/2 sums. See Kadane's algorithm en.wikipedia.org/wiki/Maximum_subarray_problem (topicstarter posted it's implementation)
|

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.