Leetcode: Longest increasing subsequence

February 8, 2016

Leetcode: Longest increasing subsequence

http://blog.csdn.net/kenden23/article/details/17632821

spend 10 minutes to read the blog:

http://www.kancloud.cn/kancloud/data-structure-and-algorithm-notes/73075

http://www.geeksforgeeks.org/dynamic-programming-set-3-longest-increasing-subsequence/

Previous blog:

http://juliachencoding.blogspot.ca/2015/06/dynamic-programming-longest-increasing.html

Write some C# code for this algorithm later.

http://buttercola.blogspot.ca/2015/12/leetcode-longest-increasing-subsequence.html

NLogn solution, better than DP solution, Recursive solution

http://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/

Set Goals:

1. Know how to solve it using recursive solution first;

2. And then, understand DP solution, how to build the formula, avoid duplication;

3. And then, know where to find optimal solution here, O(nlogn),

Julia, write some code - That is most important!

To be continued.

February 11, 2016

     More important, work on brute force solution first, and then, come out ideas to improve. Coding is next stage. 

Julia likes to work on the algorithm by herself, not depending on her experience/ memory of solved problems. So, she tried in 20 minutes to come out the idea:

Write down her analysis steps roughly:

1. Think how to use brute force solution first, 

For array 0-n, brute force solution, how many choice for length 1 subsequence - choose 1 from n,

length i subsequence - choose i from n, and then, in total, it is 2^n calculation

2. next, she thought about and had difficulty to write down and developed the idea, in 10 minutes, she decided to work on an example to help, easily she did figure out one algorithm besides brute force:
Given an array, size of 7, int[] A = {1, 8, 3, 2, 5, 4, 7}

for subarray of size 6,  1, 3, 5 - longest increasing subsequence, maximum 3, so longest one for size of 7 is 1, 3, 5, 7

But, if the array is changed to: 1, 8, 3, 2, 8, 4, 7, and then, maximum subseqence of subarray (size of 6) has two choices:

        1, 3, 8  <-    because 7 <8,  no increment

but, 1, 2, 4  <-    because 7 > 4, increment 1,  so longest subsequence is 4, so need to maintain all the sequences with length 3

And then, try to record the number of each element in the array - maximum value ends to i

1    8   3   2  8  4  7

1    2   2   2  3  3  4  <--  so, when you work on 7, you can check value ends on 3 first, to see if it can make 4, otherwise, go for 3, decrease one by one. extra space is O(N)

one more example:

2    8   3   1  8  4  7

1    2   2   1  3  3  4  <--  so, when you work on 7, you can only check value ends on 3, extra space is O(N)

Julia, that is the way you should work on the algorithm. There are thousands of problems, you cannot spend time on each one of them, you have to learn how to solve a new problem by yourself. And later, write down your improvement on the original thoughts. 

     Think about space to store the value - array, extra map for key - value list. To simplify, just go through the array from 0 to i-1, and then, compare A[i] to A[j] (j from 0 to i-1), if it is bigger, then compute maximum value. O(N^2) time complexity. 

February 12, 2016
Work on the DP solution formula - how to calculate the value based on previous one

Formula of DP: 

And then, one more advance to optimal solution (read the blog and get the idea:
http://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/):
For each sequence ends at same distance, for example, 2, you only need to keep the minimum one for future to compare, 

Here is the detail:

2    8   3   1  8  4  7

1    2   2   1  3  3  4  

Length =1
2
1

Length = 2

2 8
2 3

what if only keep 2 3, 

Length = 3

2 3 8 
2 3 4


so, for every length, keep the minimum value sequence, save space, reduce time complexity. 

How much advance in time complexity for this work? 

Julia, you are very close to the optimal solution!