Sum of the maximum downsequence number in an array.

Question

Given this array

int [] myArray = {5,-11,2,3,14,5,-14,2};

You are to find the maximum sum of the values in any downsequence in an unsorted array of integers. If the array is of length zero then maxSeqValue must return Integer.MIN_VALUE.

You should print the number, 19 because the downsequence with the maximum sum is 14,5. Downsequence number is a series of non-increasing number.

These are the codes that i used but i guess that there are some cases which is still not accounted for. Any ideas, thanks in advance.

public class MaxDownSequence{
public int maxSeqValue(int[] a){
    int sum=Integer.MIN_VALUE;
    int maxsum=Integer.MIN_VALUE;
   for (int i=1;i<a.length;i++){
        if(a[i]<a[i-1]){
            sum = a[i] + a[i-1];
            if (sum>maxsum){
                maxsum=sum;
            }
        }
        else {
            sum=a[i];
            if (sum>maxsum){
                maxsum=sum;
            }
        }
   }
   if (a.length==0){
       return Integer.MIN_VALUE;
   }
   else{
       return maxsum;

   }
}
public static void main(String args[]){
    MaxDownSequence mySeq = new MaxDownSequence();
    int [] myArray = {5,-11,2,3,14,5,-14,2};
    System.out.println(mySeq.maxSeqValue(myArray));
}

}

Answer 1

1. you haven't considered sequences of more than two numbers. If you had [3,2,1] the result should be 6. But your code would give 5, because it only looks at the sum of the current number and the previous, whereas you should keep track of a current downsequence and add the current number to the running total of that downsequence. Once you hit a number that breaks the downsequence update maxsum if needed then reset the running total to 0.

2. not sure why you have the else in the loop?? If a[i] is not less than a[i-1] then it is not a downsequence, therefore surely maxsum should not be updated. If you take just the first 3 numbers in your sample array, it would return the number 2. Because the first downsequence [5,-11] would give a sum of -6 and on the next iteration it would just look at 2, which is greater than -6 and therefore maxsum is updated.

3. No need for:

   if (a.length==0){
      return Integer.MIN_VALUE;
   }
   

   if the array length is 0 then you never enter the loop and therefore never change maxsum, so it will still be equal to Integer.MIN_VALUE, so you can just return maxsum at the end regardless.

Answer 2

Take the input {3,2,1} the answer should be 6 your program gives 5.

Your approach is correct, every time you test a number in the array you check if its less than (actually this should be <=) previous array element.

If it is you update sum as: sum = a[i] + a[i-1]; this is incorrect. sum in your program represents the running rum of the current subsequence. You should not be overwriting it.

Answer 3

Dynamic programming is the way to go.

• http://en.wikipedia.org/wiki/Dynamic_programming

I know, maybe that doesn't help at all, but since I don't want to post a solution for your problem the best thing I can do is to give you this hint :)

Answer 4

You are suppose to have a running sum i think. Meaning Sum = Sum + A[i]. Just make sure to initialize the sum to the first member of the array and you are in business.