首页 > 代码库 > Longest Increasing Continuous Subsequence
Longest Increasing Continuous Subsequence
Give an integer array，find the longest increasing continuous subsequence in this array.
An increasing continuous subsequence:
- Can be from right to left or from left to right.
- Indices of the integers in the subsequence should be continuous.
Notice
O(n) time and O(1) extra space.
Example
For [5, 4, 2, 1, 3], the LICS is [5, 4, 2, 1], return 4.
For [5, 1, 2, 3, 4], the LICS is [1, 2, 3, 4], return 4.
Runtime: 29ms
1 class Solution { 2 public: 3 /** 4 * @param A an array of Integer 5 * @return an integer 6 */ 7 int longestIncreasingContinuousSubsequence(vector<int>& A) { 8 // Write your code here 9 10 if (A.empty()) return 0;11 int result = 1;12 int leftMax = 1, rightMax = 1;13 for (int i = 1; i < A.size(); i++) {14 // from left to right15 if (A[i] > A[i - 1]) {16 leftMax++;17 rightMax = 1;18 result = max(result, leftMax);19 }20 else { // from right to left21 leftMax = 1;22 rightMax++;23 result = max(result, rightMax);24 }25 }26 return result;27 }28 };
Runtime: 838ms
1 class Solution { 2 public: 3 /** 4 * @param A an array of Integer 5 * @return an integer 6 */ 7 int longestIncreasingContinuousSubsequence(vector<int>& A) { 8 // Write your code here 9 if (A.empty()) return 0;10 11 // scan from left to right12 int leftMax = 1;13 for (int i = 1; i < A.size(); i++) {14 int j = i;15 while (j < A.size() && A[j] > A[j - 1]) j++;16 leftMax = max(leftMax, j - i + 1);17 }18 19 // scan from right to left20 int rightMax = 1;21 for (int i = A.size() - 2; i >= 0; i--) {22 int j = i;23 while (j >= 0 && A[j] > A[j + 1]) j--;24 rightMax = max(i - j + 1, rightMax);25 }26 return max(leftMax, rightMax);27 }28 };
Longest Increasing Continuous Subsequence
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。