Saturday, August 25, 2012

Sum maximum

Given an array of n positive integers. Write a program to find the sum of maximum sum subsequence of the given array such that the intgers in the subsequence are sorted in increasing order.
Pubblicato da a
Reazioni: 

1 comment:

  1. int[] A = new int[] {1, 2, 3, 20, 2, 5, 8, 20, 9, 8, 7, 6, 7, 8};

    int last = 0;
    int maxSum = 0;
    int sumSoFar = 0;
    for(int i=0; i < A.length; i++) {
    if (A[i] < last) {
    last = A[i];
    sumSoFar = last;
    continue;
    }
    sumSoFar += A[i];
    maxSum = Math.max(sumSoFar, maxSum);
    last = A[i];
    }

    System.out.println(maxSum);

    ReplyDelete

Subscribe to: Post Comments (Atom)