Given an array, find a subsequence which is longest in length and increasing in order.
Input : { 3, 4, -1, 0, 6, 2, 3 }
Output :
Max Lenght :4
Max value :7
package com.omt.learn.algo; public class LongestIncreasingSubsequence { public static void main(String[] args) { int a[] = { 3, 4, -1, 0, 6, 2, 3 }; calculateLongestincreasingSubsequence(a); } public static void calculateLongestincreasingSubsequence(int a[]) { int len[] = new int[a.length]; int val[] = new int[a.length]; val[0] = a[0]; int maxValue = 0; int maxLenght = 0; int maxValueAt = 0; int maxLengthAt = 0; for (int i = 1; i < a.length; i++) { for (int j = i - 1; j >= 0; j--) { if (a[i] > a[j]) { len[i] = len[j] + 1; val[i] = a[i] + val[j]; if (len[i] > maxLenght) { maxLenght = len[i]; maxLengthAt = i; } if (val[i] > maxValue) { maxValueAt = i; maxValue = val[i]; } break; } else { val[i] = a[i]; } } } System.out.println("Max Lenght :" + (maxLenght + 1)); System.out.println("Max value :" + maxValue); for (int v : val) { System.out.println(v); } } }