C++ 代码优化：使用动态规划提高子数组计数效率

#include #include #include #include #include #include using namespace std; typedef long long ll; const int N=1e5+10; const int P=1e9+7; ll ans; int n,a[N],last[N],cnt; struct Node{ int max; int min; }; Node dp[N]; int main(void){ scanf('%d',&n); for(int i=1;i<=n;i++){ scanf('%d',&a[i]); } for(int i=1;i<=n;i++){ memset(last, 0, sizeof(last)); cnt = 0; dp[i].max = dp[i].min = a[i]; for(int j=i;j>=1;j--){ if(last[a[j]] == 0){ cnt++; }else{ cnt = cnt - (last[a[j]] - 1); } last[a[j]] = j; dp[i].max = max(dp[i].max, a[j]); dp[i].min = min(dp[i].min, a[j]); ans += cnt; ans %= P; } } printf('%lld',ans); return 0; }