text: // Source : https://leetcode.com/problems/increasing-triplet-subsequence/
  // Author : Calinescu Valentin, Hao Chen
  // Date   : 2016-02-27
  
  /*************************************************************************************** 
   *
   * 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.
   * Your algorithm should run in O(n) time complexity and O(1) space complexity.
   * 
   * Examples:
   * Given [1, 2, 3, 4, 5],
   * return true.
   * 
   * Given [5, 4, 3, 2, 1],
   * return false.
   * 
   ***************************************************************************************/
  class Solution {
  public:
      bool increasingTriplet(vector<int>& nums) {
          bool solution = false;
          if(nums.size())
          {
              int first = nums[0];
              int second = 0x7fffffff; //MAX_INT so we can always find something smaller than it
              for(int i = 1; i < nums.size() && !solution; i++)
              {
                  if(nums[i] > second)
                      solution = true;
                  else if(nums[i] > first && nums[i] < second)
                      second = nums[i];
                  else if(nums[i] < first)
                      first = nums[i];
              }
          }
          return solution;
      }
  };
  
  
  //Hao Chen's implementation
  class Solution {
  public:
      bool increasingTriplet(vector<int>& nums) {
          if (nums.size() < 3) return false;
          
          int first=INT_MAX, second = INT_MAX;
          
          for(int i=0; i<nums.size(); i++) {
              if ( first > nums[i] ) {
                  first = nums[i];
              }else if ( first < nums[i] && nums[i] < second) {
                  second = nums[i];
              }else if (nums[i] > second){
                  return true;
              }
          }
          return false;
      }
  };
  