Longest ascending subsequence-dynamic programming

Problem description

Given an unordered array of integers, find the length of the longest ascending subsequence.

Example:

Input: [10, 9, 2, 5, 3, 7, 101, 18]
Output: 4 
Interpretation: The longest ascending subsequence is [2,3,7,101], and its length is 4.

Explain:

There may be multiple combinations of the longest ascending subsequences, you just need to output the corresponding length.
The time complexity of your algorithm should be O(n2).
Advancement: Can you reduce the time complexity of the algorithm to O(n log n)?

Solving problems

Dynamic programming: time complexity requiring O(n2)
1. Create an array dp that records the longest subsequence length for each location
2. Traverse the array from left to right, look at the number in front of it at each location, and find the largest subsequence that is smaller than the current number.
3. Find the longest subsequence length by traversing dp
Dynamic programming + binary search:
1. Create an array dp to record the longest subsequence and use len to record the length of the subsequence.
2. Traverse the array and find the current number in the DP array. If it is larger than all the numbers, it will be added after the current dp.
If it is not greater than all the numbers, find the first one larger than the current number and replace it.
3. The length of the last digit in dp is the length of the longest subsequence

Code

Dynamic planning:

package solution;


class Solution {
    public int lengthOfLIS(int[] nums) {
        //Record the maximum suborder of each location
        int[] dp=new int[nums.length];
        for(int i=0;i<nums.length;i++) {
            dp[i]=1;
            for(int j=i-1;j>=0;j--){
                //If the preceding number is less than the current number
                if(nums[j]<nums[i])
                dp[i]=Math.max(dp[i],dp[j]+1);//Find the largest suborder ahead
            }
        }
        int max=Integer.MIN_VALUE;
        //Traversing to Find the Maximum Suborder
        for (int i:dp
             ) {
            if(i>max){
                max=i;
            }
        }
        return max;
    }
}

Dynamic Programming + Binary Search

package solution;


class Solution {
    public static void main(String[] args) {
        Solution solution=new Solution();
        solution.lengthOfLIS(new int[]{10,9,2,5,3,7,101,18});
    }
    public int lengthOfLIS(int[] nums) {
       int[] dp=new int[nums.length];
       int len=0;
       for (int num:nums) {
       		//Find numbers larger than num
           int i = binarySearch(dp,0,len,num);
           if(i<0){
               i=-(i+1);
           }
           dp[i]=num;
           if(i==len){
               len++;
           }
       }
       return len;
    }
    //Two points search
    private int binarySearch(int[] dp,int start,int end,int num){
        int low=start;
        int high=end-1;
        while (low<=high){
            int mid=low+((high-low)>>>1);//Equivalent to (high+low)/2, the former can avoid integer crossing
            int midVal=dp[mid];
            if(midVal>num){
                high=mid-1;
            }else if(midVal<num){
                low=mid+1;
            }else {
                return mid;
            }
        }
        return -(low+1);
    }
}

Tags: Programming less

Posted on Sun, 06 Oct 2019 02:25:39 -0700 by pthurmond