uopspop

Untitled

Oct 4th, 2019
132
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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. }
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×