Random commentary about Machine Learning, BigData, Spark, Deep Learning, C++, STL, Boost, Perl, Python, Algorithms, Problem Solving and Web Search

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.

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

ReplyDeleteint 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);