Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- public class DP_Longest_Increasing_Sequence {
- public static void main(String[] args) {
- int[] testary = new int[]{5, 2, 8, 6, 3, 6, 9, 7};
- Integer longest = dp_LIS(testary);
- System.out.println("result:" + longest);
- System.out.println();
- }
- private static int dp_LIS(int[] testary) {
- int[] longestIncreasingSequence = new int[testary.length];
- // initialize the longestIncreasingSequence
- for (int i = 0; i < longestIncreasingSequence.length; i++) {
- longestIncreasingSequence[i] = Integer.MIN_VALUE;
- }
- longestIncreasingSequence[0] = 1; // the initial state
- // take each vertex as the destination per round
- // build the longestIncreasingSequence[] from small to large, so that large can reuse the small part
- for (int i = 1; i < testary.length; i++) {
- // the number of edge
- int maxPre = 0;
- for (int j = i - 1; j >= 0; j--) {
- // check sequence
- if (testary[j] < testary[i]) {
- // we found a smaller number in the left side of the current node
- System.out.printf("found pre num: %d <- %d %n", j, i);
- if (longestIncreasingSequence[j] > maxPre) {
- maxPre = longestIncreasingSequence[j]; // DP: we reuse the value each run to avoid repeat work
- }
- }
- }
- longestIncreasingSequence[i] = 1 + maxPre;
- }
- // pick the longest one among all destinations
- int longest = Integer.MIN_VALUE;
- for (int i = 0; i < longestIncreasingSequence.length; i++) {
- if (longestIncreasingSequence[i] > longest) {
- longest = longestIncreasingSequence[i];
- }
- }
- return longest;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement