Try LIS


  • 0
    F

    Though O(n^2)

    class Solution {
        public boolean increasingTriplet(int[] nums) {
            if (nums == null || nums.length < 3) {
                return false;
            }
            int maxlen = LIS(nums);
            if (maxlen >= 3) {
                return true;
            }
            return false;
        }
        private int LIS(int[] nums) {
            int res = 0;
            int[] dp = new int[nums.length];
            Arrays.fill(dp, 1);
            for (int i = 0; i < nums.length; i++) {
                for (int j = 0; j < i; j++) {
                    if (nums[i] > nums[j]) {
                        dp[i] = Math.max(dp[i], dp[j] + 1);
                    }
                }
            }
            
            for (int num : dp) {
                res = Math.max(res, num);
            }
            
            return res;
        }
    }
    

Log in to reply
 

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