Advertisement
uopspop

Untitled

Oct 4th, 2019
215
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.87 KB | None | 0 0
  1. public class DP_Longest_Increasing_Sequence {
  2.  
  3.     public static void main(String[] args) {
  4.  
  5.         int[] testary = new int[]{5, 2, 8, 6, 3, 6, 9, 7};
  6.         Integer longest = dp_LIS(testary);
  7.         System.out.println("result:" + longest);
  8.         System.out.println();
  9.     }
  10.  
  11.     private static int dp_LIS(int[] testary) {
  12.         int[] longestIncreasingSequence = new int[testary.length];
  13.  
  14.         // initialize the longestIncreasingSequence
  15.         for (int i = 0; i < longestIncreasingSequence.length; i++) {
  16.             longestIncreasingSequence[i] = Integer.MIN_VALUE;
  17.         }
  18.         longestIncreasingSequence[0] = 1; // the initial state
  19.  
  20.         // take each vertex as the destination per round
  21.         // build the longestIncreasingSequence[] from small to large, so that large can reuse the small part
  22.         for (int i = 1; i < testary.length; i++) {
  23.  
  24.             // the number of edge
  25.             int maxPre = 0;
  26.             for (int j = i - 1; j >= 0; j--) {
  27.                 // check sequence
  28.                 if (testary[j] < testary[i]) {
  29.                     // we found a smaller number in the left side of the current node
  30.                     System.out.printf("found pre num: %d <- %d %n", j, i);
  31.                     if (longestIncreasingSequence[j] > maxPre) {
  32.                         maxPre = longestIncreasingSequence[j]; // DP: we reuse the value each run to avoid repeat work
  33.                     }
  34.                 }
  35.             }
  36.  
  37.             longestIncreasingSequence[i] = 1 + maxPre;
  38.         }
  39.  
  40.         // pick the longest one among all destinations
  41.         int longest = Integer.MIN_VALUE;
  42.         for (int i = 0; i < longestIncreasingSequence.length; i++) {
  43.             if (longestIncreasingSequence[i] > longest) {
  44.                 longest = longestIncreasingSequence[i];
  45.             }
  46.         }
  47.  
  48.         return longest;
  49.     }
  50.  
  51.  
  52. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement