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