原题链接在这里：

题目：

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.

Note: Your algorithm should run in O(n) time complexity and O(1) space complexity.

Example 1:

Input: [1,2,3,4,5]Output: true

Example 2:

Input: [5,4,3,2,1]Output: false

题解：

Could use dp to track up to index i, the length of longest subarray. 

For all j from 0 to i, if nums[j]<nums[i], then dp[i] = Math.max(dp[i], dp[j]+1). If dp[i] >= 3, then return true.

Time Complexity: O(n^2). n = nums.length.

Space: O(n).

AC Java: 

1 class Solution { 2     public boolean increasingTriplet(int[] nums) { 3         if(nums == null || nums.length < 3){ 4             return false; 5         } 6          7         int len = nums.length; 8         int [] dp = new int[len]; 9         for(int i = 0; i
     
       2){15                         return true;16                     }17                 }18             }19         }20         21         return false;22     }23 }
     

Could use first and second variables to maintain the first smallest and second smallest number.

For each number in nums array, if num <= first, update first. Else if num <= second, update second. Else, this means that there are 2 increasing numbers smaller than current number before. Thus return true.

Time Complexity: O(n).

Space: O(1).

AC Java:

1 class Solution { 2     public boolean increasingTriplet(int[] nums) { 3         int first = Integer.MAX_VALUE; 4         int second = Integer.MAX_VALUE; 5         for(int num : nums){ 6             if(num <= first){ 7                 first = num; 8             }else if(num <= second){ 9                 second = num;10             }else{11                 return true;12             }13         }14         15         return false;16     }17 }

类似.