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.
Have you met this question in a real interview?
Yes
Example
For[5, 4, 2, 1, 3]
, the LICS is[5, 4, 2, 1]
, return4
.
For[5, 1, 2, 3, 4]
, the LICS is[1, 2, 3, 4]
, return4
.
line 18 should be end < start , not start < end. know every line meaning , draw them out to make less mistakes
better use template on fucntions with vector iterator and reverse_iterator to reuse code.
and decltype keyword
class Solution {
public:
/\*\*
\* @param A an array of Integer
\* @return an integer
\*/
int longestIncreasingContinuousSubsequence\(vector<int>& A\) {
if \(A.empty\(\)\) {
return 0;
}
// Write your code here
int left2right = search< decltype\(A.begin\(\)\) >\(A, A.begin\(\), A.end\(\)\);
// cout<< left2right << endl;
int right2left = search< decltype\(A.rbegin\(\)\) >\(A, A.rbegin\(\), A.rend\(\)\);
// cout << right2left<<endl;
return max\(left2right, right2left\);
}
private:
template <typename Iter>
int search\(vector<int>& A, Iter start, Iter end\) {
if \(end < start\) {
return 0;
}
int max = 1, curLen = 1;
for \(Iter it = start; it < end; ++it\) {
if \( \*it <= \*\(it + 1\) \) {
curLen++;
if \(curLen > max\) {
max = curLen;
}
} else {
curLen = 1;
}
}
return max;
}
};