LintCode 76 · Longest Increasing Subsequence

The dp: function is
dp[i] = Math.max(dp[i], dp[l] + 1);

	public class Solution {
	/**
	* @param nums: An integer array
	* @return: The length of LIS (longest increasing subsequence)
	*/
	public int longestIncreasingSubsequence(int[] nums) {
	// write your code here
	if (nums == null || nums.length == 0) {
	return 0;
	}
	int max = 0;
	int n = nums.length;
	int[] dp = new int[n];
	Arrays.fill(dp, 1);
	for (int i = 0; i < n; i++) {
	for (int l = 0; l < i; l++) {
	if (nums[i] > nums[l]) {
	dp[i] = Math.max(dp[i], dp[l] + 1);
	}
	}
	max = Math.max(max, dp[i]);
	}
	System.out.println("Arrays.toString(dp) = " + Arrays.toString(dp));
	return max;
	}
	}

view raw LintCode76 · Longest Increasing Subsequence.java hosted with ❤ by GitHub