202109-2 非零段划分

• C++
• 总结

本题链接：202109-2 非零段划分

本博客给出本题截图：

#include 
#include 

using namespace std;

const int N = 500010;
 
int a[N], b[N];
 
int main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i ++ )
    {
        cin >> a[i];
        if(a[i] > a[i - 1])
        {
            b[a[i - 1]] ++;
            b[a[i]] --;
        }
    }
    int ans = 0, t = 0;
    for(int i = 0;i < N;i ++ )
    {
        t += b[i];
        ans = max(ans, t);
    }
    cout << ans << endl;
    
    return 0;
}

标准的一道前缀和 + 差分的题目（这几次考试第二题好像都设计前缀和的思想了
前缀和
差分