Java Solution (For DP practice only)


  • 0

    Here is my Java solution, because I am new to DP and I pick this problem to practice my DP basic skill, I don't mean to optimize the solution to be the best, just share, but suggestions are still welcome, thanks in advance,

    public class Solution300LongestIncreasingSubsequence {
    
    	public int lengthOfLIS(int[] nums) {
    		if (nums == null || nums.length == 0)
    			return 0;
    
    		int[] dp = new int[nums.length];
    		for (int i = 0; i < dp.length; i++)
    			dp[i] = 1;
    
    		for (int i = 1; i < nums.length; i++)
    			for (int j = i - 1; j >= 0; j--)
    				if (nums[i] > nums[j] && dp[i] < dp[j] + 1)
    					dp[i] = dp[j] + 1;
    
    		int max = dp[0];
    		for (int i = 1; i < dp.length; i++)
    			if (dp[i] > max)
    				max = dp[i];
    
    		return max;
    	}
    }
    

Log in to reply
 

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