Description
You are given a list of integers nums. Return the length of the longest sublist such that its length is at least 3 and its values are strictly increasing and then decreasing. Both the increasing part and the decreasing part must be non-empty.
Constraints:
-
n ≤ 100,000wherenis the length ofnums
Example 1
Input
nums = [7, 1, 3, 5, 2, 0]
Output
5
Explanation
The sublist [1, 3, 5, 2, 0] is strictly increasing then decreasing.
Example 2
Input
nums = [1, 2, 3]
Output
0
Example 3
Input
nums = [3, 2, 1]
Output
0
Example 4
Input
nums = [1, 2, 1, 1]
Output
3
Intuition
- increase array
-
inc[i]: increase length from0toi
-
- decrease array
-
dec[i]: decrease length fromitoend
-
Implementation
int solve(vector<int>& nums) {
int n = nums.size();
vector<int> inc(n, 1), dec(n, 1);
// inc[i]: increase length from 0 to i
for (int i = 1; i < n; i++) {
if (nums[i] > nums[i - 1]) {
inc[i] = inc[i - 1] + 1;
}
}
// dec[i]: decrease length from i to end
for (int i = n - 2; i >= 0; i--) {
if (nums[i] > nums[i + 1]) {
dec[i] = dec[i + 1] + 1;
}
}
int res = 0;
for (int i = 0; i < n; i++) {
if (inc[i] > 1 && dec[i] > 1) {
res = max(res, inc[i] + dec[i] - 1);
}
}
return res;
}
Time Complexity
- Time: O(n)
- Space: O(n)
Top comments (0)