202109-2 非零段划分

#include <bits/stdc++.h> //70分 30分超时
using namespace std;
const int maxn = 500005;
int n, N;
int a[maxn];
int b[maxn];
int vis[maxn];
 
int main()
{
   cin >> n;
   for (int i = 1; i <= n; i++)
   {
      cin >> a[i];
   }
   int p = 0;
   int ans11 = 0;
   for (int i = 1; i <= n; i++)
   {
      int b[maxn] = {0};
      int ans = 0;
      if(vis[a[i]]==1) continue;
      p = a[i];
      vis[a[i]]=1;
      for (int j = 1; j <= n; j++)
      {
         if (a[j] < p)
         {
         }
         else
         {
            b[j] = a[j];
         }
      }
      for (int j = 1; j <= n; j++)
      {
         if (b[j] != 0 && b[j - 1] == 0)
         {
            ans++;
         }
      }
      if (ans > ans11)
      {
 
         ans11 = ans;
      }
   }
   cout << ans11;
}

#include <bits/stdc++.h> //100分
using namespace std;
const int maxn = 500005;
int n;
int a[maxn];
int cnt[maxn];
 
int main() // 类似岛屿问题优化  后缀和
{
   cin >> n;
   int max1 = 0;
   for (int i = 1; i <= n; i++)
   {
      cin >> a[i];
      max1 = max(max1, a[i]);
   }
   a[0] = 0;
   a[n + 1] = 0;                 // 边界默认为0
   n = unique(a, a + n + 2) - a; // a[0]到a[n+1]都要unique
   // 要-a  此时不存在相邻处相同的情况
   // unique很重要，这里只需考虑相邻元素不同的情况
   for (int i = 1; i < n; i++)
   {
      if (a[i - 1] < a[i] && a[i] > a[i + 1])
      { // 凸峰
         cnt[a[i]]++;
      }
      else if (a[i - 1] > a[i] && a[i] < a[i + 1])
      { // 凹谷
         cnt[a[i]]--;
      }
   }
   int res = 0, sum = 0;
   for (int i = max1 + 100; i >= 1; i--)
   {
      sum += cnt[i];
      res = max(res, sum);
   }
   cout << res;
}