# My easy to understand O(n^2) solution using DP with video explanation

• This solution is taken from this great guy -
https://www.youtube.com/watch?v=CE2b_-XfVDk

``````    public int lengthOfLIS(int[] nums)
{
// Base case
if(nums.length <= 1)
return nums.length;

// This will be our array to track longest sequence length
int T[] = new int[nums.length];

// Fill each position with value 1 in the array
for(int i=0; i < nums.length; i++)
T[i] = 1;

// Mark one pointer at i. For each i, start from j=0.
for(int i=1; i < nums.length; i++)
{
for(int j=0; j < i; j++)
{
// It means next number contributes to increasing sequence.
if(nums[j] < nums[i])
{
// But increase the value only if it results in a larger value of the sequence than T[i]
// It is possible that T[i] already has larger value from some previous j'th iteration
if(T[j] + 1 > T[i])
{
T[i] = T[j] + 1;
}
}
}
}

// Find the maximum length from the array that we just generated
int longest = 0;
for(int i=0; i < T.length; i++)
longest = Math.max(longest, T[i]);

return longest;
}``````

• Why do I need to fill dp with 1? Can't I just do dp[0] = 1 before the loop?

• I think filling dp with 1s can help handle the case when nums[i] is smaller than all nums[j]. You can of course do something to keep track of whether all nums[j] are bigger than nums[i], and when that happens you fill dp[i] with 1, but that seems to be a lot more complicated than filling the whole array with 1s.

• this is regular DP question, exactly the same as mine

• I think you don't need to fill array T with ones, you just need to plus one when you return the longest.

• ``````public static int lengthOfLIS2(int[] nums) {
if(nums.length == 0 || nums == null){
return 0;
}
int []dp = new int[nums.length];
int max = Integer.MIN_VALUE;
for (int i = 0; i < nums.length; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
dp[i] = dp[i] > dp[j] + 1 ? dp[i] : dp[j] + 1;
}
}
if (dp[i] > max) {
max = dp[i];
}
}
return max;
}``````

• ``````public int lengthOfLIS(int[] nums) {
if(nums==null || nums.length == 0 ) return 0;

int[] dp = new int[nums.length];
int max = Integer.MIN_VALUE;
for( int i=0; i<nums.length; i++ ){
dp[i] = 1;
for( int j=0; j<i; j++ ){
if(nums[j]<nums[i]){
dp[i] = Math.max(dp[i],dp[j]+1);
}
}
if (dp[i] > max) {
max = dp[i];
}
}

return max;
}``````

• Thanks for the link to the video.
The video is very helpful.

One thing:

``````Arrays.fill(T, 1);
``````

which looks concise.

• i suppose `T[j]` would never actually exceed `T[i]`, so `if(T[j] == T[i])` shall also good to work instead of `if(T[j] + 1 > T[i])`.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.