Documentation·
acmjec/CompetitiveCoding_Hacktoberfest2024
Add longest increasing subsequence problem with Java solution
Adds Microsoft/Problem18.md with a longest strictly increasing subsequence problem and a Java dynamic programming solution. The example demonstrates a subsequence length of four.
The problem
The task is to compute the length of the longest strictly increasing subsequence in an integer array. The solution must preserve element order while allowing elements to be skipped, and equal values must not extend a subsequence.
The approach
The implementation initializes a dynamic programming array with a subsequence length of one for each element. For each position, it checks earlier positions and extends their subsequences only when the current value is strictly larger. It returns the maximum recorded length, with an explicit return of zero for an empty array.
What changed
The new Markdown file supplies the problem statement, example input, and Java implementation with a main method whose documented output is four. The implementation uses quadratic time and linear auxiliary space.
- java
- dynamic-programming
- arrays
- longest-increasing-subsequence
- competitive-programming