300. Longest Increasing Subsequence

Let dp[i] be the longest increasing subsequence till i. We need to move pointer from 1 to n-1 and for element i, we need to check from 0 to i-1, dp[i] = dp[j] + 1 if nums[i] > nums[j] and dp[j]+1 > dp[i].

1:  class Solution {  
2:  public:  
3:    int lengthOfLIS(vector<int>& nums) {  
4:      vector<int> dp(nums.size(), 1);  
5:      int maxLen = 0;  
6:      for (int i = 1; i < nums.size(); i++) {  
7:        for (int j = 0; j < i; j++) {  
8:          if (nums[j] < nums[i] && dp[i] < dp[j]+1) {  
9:            dp[i] = dp[j] + 1;  
10:          }  
11:        }  
12:      }  
13:      for (int i = 0; i < nums.size(); i++) {  
14:        maxLen = max(maxLen, dp[i]);  
15:      }  
16:      return maxLen;  
17:    }  
18:  };  

When I revisited this problem, the greedy algorithm seems working too. The idea is to keep an LIS vector, when the new number comes in, check it against the LIS, and replace the first number in LIS that is larger than the new number if any. Therefore the LIS always keeps the smallest increasing sequence and thus reaches the largest possibility to grow. With this algorithm, the searching can be modified to binary search in this algorithm so it can be improved to nlogn even faster than the DP.

1:  class Solution {  
2:  public:  
3:    int lengthOfLIS(vector<int>& nums) {  
4:      vector<int> lis;  
5:      for (int i = 0; i < nums.size(); i++) {  
6:        if (lis.empty() || nums[i] > lis[lis.size()-1]) lis.push_back(nums[i]);  
7:        else if (nums[i] > lis[0] || nums[i] < lis[lis.size()-1]) {  
8:          int j = 0;  
9:          while (nums[i] > lis[j]) j++;  
10:          lis[j] = nums[i];  
11:        }  
12:      }  
13:      return lis.size();  
14:    }  
15:  };