## Java solution for “Longest Increasing Subsequence”

### The Problem

In computer science, the longest increasing subsequence problem is to find a subsequence of a given sequence in which the subsequence’s elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous, or unique.

https://en.wikipedia.org/wiki/Longest_increasing_subsequence

### My solution

This is what I came up with (albeit in a short timeframe); it’s not the best or most efficient!

### Main.java

```package com.lstierneyltd.examples;

public class Main {
public static void main(String[] args) throws Exception {
final LongestIncreasingSubsequenceSolver solver =
new LongestIncreasingSubsequenceSolver();

solver.init(new int[]{10, 22, 9, 33, 21, 50, 41, 60});
solver.solve(); // 5

// Van der Corput sequence
solver.init(new int[]{0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15});
solver.solve(); // 6

}
}
```

### LongestIncreasingSubsequenceSolver.java

```package com.lstierneyltd.examples;

import java.util.ArrayList;
import java.util.List;
public class LongestIncreasingSubsequenceSolver {
private int inputLength;
private List<Integer> sequence;
private List<Integer> input;

public void init(final int[] inputArray) {
inputLength = inputArray.length;
input = new ArrayList<>(inputLength);
sequence = new ArrayList<>(inputLength);

int i;
for (i = 0; i < inputLength; i++) {
}

for (i = 0; i < inputLength; i++) {
}
}

public void solve() {
int i, j, max = 0;

for (i = 1; i < inputLength; i++) {
for (j = 0; j < i; j++) {
if (input.get(i) > input.get(j) && sequence.get(i) < sequence.get(j) + 1) {
sequence.set(i, sequence.get(j) + 1);
}
}
}
for (i = 0; i < inputLength; i++) {
if (max < sequence.get(i)) {
max = sequence.get(i);
}
}
System.out.println("The Longest Subsequence length was: " + max);
}
}
```

XHTML: You can use these tags: `<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> `