Acwing 1490. 最长上升子串

Acwing 1490. 最长上升子串

思路：

[i] : 以i为结尾的最长子串长度
g[i] : 以i为起点的最长子串长度

最后枚举每一个点，如果a[i - 1] < a[i + 1] res = max(res,f[i - 1] + g[i + 1])
否则 res = max(res,max(f[i - 1], g[i + 1]));
代码：

#include<iostream>
using namespace std;
const int N = 1e5+10;
int n;
int a[N];
int f[N];
int g[N];

int main(){
    cin>>n;
    for(int i = 1; i <= n; i++) cin>>a[i];
    int res = 0;
    //f[i] 以i结尾的最长上升子串
    for(int i = 1; i <= n; i++){
        if(a[i - 1] < a[i]) f[i] = f[i - 1] + 1;
        else f[i] = 1;
    }
    //g[i] 以i为起点的最长上升子串
    for(int i = n; i >= 0; i--){
        if(a[i] < a[i + 1]) g[i] = g[i + 1] + 1;
        else g[i] = 1;
    }
    
    for(int i = 1; i <= n; i++){
        if(a[i - 1] < a[i + 1]) res = max(res,f[i - 1] + g[i + 1]);
        else res = max(res,max(f[i - 1],g[i + 1]));
    }
    cout<<res;
    return 0;
}