title: (LIS) Longest Increasing Subsequence Algorithm
body: <p><strong>EDIT</strong>
  <br>
  Finally, I found this "Brute force" method is not right.
  <br>So I write another two methods to solve the LIS problem.</p>
  
  <ul>
  <li>Using LCS on the original array and the sorted array. Time complexity = (n^2).</li>
  <li>Using DP + Binary search. Time complexity = O(nlgn).</li>
  </ul>
  
  <p><strong>[The code is at the end.]</strong></p>
  
  <p><hr>
  I try to use brute force to find Longest Increasing Subsequence (LIS).
  But personally I think the time complexity of this algorithm is O(n<sup>2</sup>), which is equal to the DP approach, is it correct?</p>
  
  <pre><code>// Find LIS Brute force.
  public static int[] findLIS_BF (int[] givenArray) {
      int size = givenArray.length;
      int maxLen = Integer.MIN_VALUE;
      int prevIndex = 0;
      int tempLen = 1;
      int head = 0;
      for (int tempHead = 0; tempHead &lt; size; tempHead ++) {
          prevIndex = tempHead;
          tempLen = 1;
          for (int subPointer = tempHead + 1; subPointer &lt; size; subPointer ++) {
              if (givenArray[prevIndex] &lt;= givenArray[subPointer]) {
                  prevIndex = subPointer;
                  tempLen ++;
              }
          }
          if (tempLen &gt; maxLen) {
              maxLen = tempLen;
              head = tempHead;
          }
      }
  
      System.out.println("LIS by BF, max len = " + maxLen);
      int[] rest = new int[maxLen];
      int restIndex = 0;
      rest[restIndex] = givenArray[head];
      restIndex ++;
      prevIndex = head;
      for (int i = head + 1; i &lt; size; i ++) {
          if (givenArray[prevIndex] &lt;= givenArray[i]) {
              rest[restIndex] = givenArray[i];
              restIndex ++;
              prevIndex = i;
          }
      }
      return rest;
  }
  </code></pre>
  
  <p><hr>
  <strong>[EDIT]</strong><br>
  <strong>[LCS Method]</strong><br></p>
  
  <pre><code>public class FindLIS_LCS {
  
  // Find LIS by LCS.
  // Time complexity = O(n^2).
  // LCS.
  // Time complexity = O(n^2).
  // Note:
  // UP LEFT MARK = -1.
  // UP MARK = -2.
  // LEFT MARK = -3.
  private static int LCS (int[] firstA, int[] secondA, int[][]c, int[][]b) {
      int lenFA = firstA.length;
      int lenSA = secondA.length;
  
      // Init c matrix.
      for (int i = 0; i &lt; lenFA; i ++) c[i][0] = 0;
      for (int i = 0; i &lt; lenSA; i ++) c[0][i] = 0;
  
      for (int i = 1; i &lt; lenFA+1; i ++) {
          for (int j = 1; j &lt; lenSA+1; j ++) {
              if (firstA[i - 1] == secondA[j - 1]) {
                  c[i][j] = c[i - 1][j - 1] + 1;
                  b[i - 1][j - 1] = -1;
              } else if (c[i - 1][j] &gt;= c[i][j - 1]) {
                  c[i][j] = c[i - 1][j];
                  b[i - 1][j - 1] = -2;
              } else {
                  c[i][j] = c[i][j - 1];
                  b[i - 1][j - 1] = -3;
              }
          }
      }
      return c[lenFA][lenSA];
  }
  
  // Print out the LCS.
  // Time complexity = O(m + n).
  private static void printLCS_Helper (int[] firstA, int[][]b, int i, int j) {
      if (i &lt; 0 || j &lt; 0) return; // Base case.
      if (b[i][j] == -1) {
          printLCS_Helper(firstA, b, i - 1, j - 1);
          System.out.print(String.format("%-6d", firstA[i]));
      } else if (b[i][j] == -2) printLCS_Helper(firstA, b, i - 1, j);
      else printLCS_Helper(firstA, b, i, j - 1);
  }
  public static void printLCS (int[] firstA, int[][]b) {
      int size = firstA.length;
      printLCS_Helper(firstA, b, size - 1, size - 1);
  }
  
  // Quick sort for array.
  // Time complexity = O(nlgn).
  private static void exchange (int[] givenArray, int firstIndex, int secondIndex) {
      int temp = givenArray[firstIndex];
      givenArray[firstIndex] = givenArray[secondIndex];
      givenArray[secondIndex] = temp;
  }
  private static int partition (int[] givenArray, int start, int end, int pivotIndex) {
      int pivot = givenArray[pivotIndex];
      int left = start;
      int right = end;
      while (left &lt;= right) {
          while (givenArray[left] &lt; pivot) left ++;
          while (givenArray[right] &gt; pivot) right --;
          if (left &lt;= right) {
              exchange(givenArray, left, right);
              left ++;
              right --;
          }
      }
      return left;
  }
  private static void quickSortFromMinToMax_Helper (int[] givenArray, int start, int end) {
      if (start &gt;= end) return; // Base case.
      // Generate a random num in the range[start, end] as the pivot index to partition the array.
      int rand = start + (int) (Math.random() * ((end - start) + 1));
      int split = partition (givenArray, start, end, rand);
      // Do recursion.
      quickSortFromMinToMax_Helper(givenArray, start, split - 1);
      quickSortFromMinToMax_Helper(givenArray, split, end);
  }
  public static void quickSortFromMinToMax (int[] givenArray) {
      int size = givenArray.length;
      quickSortFromMinToMax_Helper(givenArray, 0, size - 1);
  }
  
  // Copy array.
  public static int[] copyArray (int [] givenArray) {
      int size = givenArray.length;
      int[] newArr = new int[size];
      for (int i = 0; i &lt; size; i ++) 
          newArr[i] = givenArray[i];
      return newArr;
  }
  
  // Main method to test.
  public static void main (String[] args) {
      // Test data: {1, 2, 1, 4, 5, 3, 10}.
      //int[] givenArray = {1, 2, 1, 4, 5, 3, 10};
      int[] givenArray = {2, 1, 6, 3, 5, 4, 8, 7, 9};
      int size = givenArray.length;
      // Test finding LIS by LCS approach.
      int[] sortedArr = copyArray(givenArray);
      quickSortFromMinToMax (sortedArr);
      int[][]c = new int[size + 1][size + 1];
      int[][]b = new int[size][size];
      System.out.println("Test max len = " + LCS(givenArray, sortedArr, c, b));
      printLCS(givenArray, b);
  }
  }
  </code></pre>
  
  <p><strong>[DP + Binary Search Method]</strong></p>
  
  <pre><code>public class FindLIS {
  
  // Linear search.
  public static int linearSearch (int[] givenArray, int key) {
      int size = givenArray.length;
      for (int i = size - 1; i &gt;= 0; i --) {
          if (givenArray[i] &gt;= 0) 
              if (givenArray[i] &lt; key) return i;
      }
      return -1;
  }
  
  // Find the len of the LIS.(Longest increasing (non-necessarily-adjacent) subsequence).
  // DP + Binary search.
  // Time complexity = O(nlgn).
  // Note:
  // This binary search to find the elem's index of the given array, which is less than the elem's value = key.
  private static int biSearch (int[] givenArray, int start, int end, int key) {
      if (start &gt; end) return -1;
      int mid = (start + end) / 2;
      if (givenArray[mid] &lt;= key) return mid;
      else return biSearch(givenArray, start, mid - 1, key);
  }
  
  public static int findLISLen (int[] givenArray) {
      int size = givenArray.length;
      int maxLen = 1;
      int[] memo = new int[size];
      for (int i = 0; i &lt; size; i ++) memo[i] = -10;
      memo[0] = givenArray[0];
  
      for (int i = 1; i &lt; size; i ++) {
          if (givenArray[i] &gt; memo[maxLen - 1]) {
              memo[maxLen] = givenArray[i];
              maxLen ++;
          } else {
              // int pos = linearSearch(memo, givenArray[i]); // Using linear search, the time complexity = O(n^2).
              int pos = biSearch(memo, 0, maxLen - 1, givenArray[i]); // Using Binary search, the time complexity = O(nlgn).
              memo[pos + 1] = givenArray[i];
          }
      }
      // Show memo.
      showArray(memo);
      return maxLen;
  }
  
  
  // Show array.
  public static void showArray (int[] givenArray) {
      int size = givenArray.length;
      for (int i = 0; i &lt; size; i ++) 
          System.out.print(String.format("%-6d", givenArray[i]));
      System.out.println();
  }
  
  // Main method to test.
  public static void main (String[] args) {
      // Test data: {2, 1, 6, 3, 5, 4, 8, 7, 9}.
      //int[] givenArray = {2, 1, 6, 3, 5, 4, 8, 7, 9};
      //int[] givenArray = {1, 2, 1, 4, 5, 3, 10};
      int[] givenArray = {2, 1, 6, 3, 5, 4, 8, 7, 9};
  
      // Test finding the LIS by DP + Binary search.
      System.out.println("Test finding the LIS by DP + Binary search, max len = " + findLISLen(givenArray));
  
  }
  }
  </code></pre>