Question

Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.

Formally the function should:

Return true if there exists i, j, k such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false.

Example:

Input: [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Thinking:

  • Method:
    • DP
class Solution {
    public boolean increasingTriplet(int[] nums) {
        if(nums == null || nums.length < 3) return false;
        int len = nums.length;
        int[] dp = new int[len + 1];
        for(int i = 1; i <= len; i++){
            dp[i] = 1;
            int cmp = nums[i - 1];
            for(int j = 0; j < i - 1; j++){
                if(nums[j] < cmp){
                    dp[i] = Math.max(dp[i], dp[j + 1] + 1);
                }
                if(dp[i] >= 3) return true;
            }
        }
        return false;
    }
}
  • Method 2:
class Solution {
    public boolean increasingTriplet(int[] nums) {
        int m1 = Integer.MAX_VALUE, m2 = Integer.MAX_VALUE;
        for(int num : nums){
            if(m1 >= num) m1 = num;
            else if(m2 >= num) m2 = num;
            else return true;
        }
        return false;
    }
}
  • Method 3
    • 从前向后，取最小值in。
    • 从后向前，取最大值de。
    • 原来的数小于in大于de。
class Solution {
    public boolean increasingTriplet(int[] nums) {
        if(nums == null || nums.length < 3) return false;
        int len = nums.length;
        int[] in = new int[len];
        int[] de = new int[len];
        de[0] = nums[0];
        for(int i = 1; i < len; i++){
            de[i] = Math.min(de[i - 1], nums[i]);
        }
        in[len - 1] = nums[len - 1];
        for(int i = len - 2; i >= 0; i--){
            in[i] = Math.max(in[i + 1], nums[i]);
        }
        for(int i = 0; i < len; i++)
            if(nums[i] > de[i] && nums[i] < in[i]) return true;
        return false;
    }
}