CSP202109-1 数组推导

题意

给出数组$A$的前缀最大值数组$B$，求数组$A$可能的和的最大值与最小值
数据范围：$n\le 100,0\le B_i\le 10^5$

题解

1. $100\%$数据
   易知数组$B$单调不降
   当数组$B$发生改变，即$B[i]\ne B[i-1]$时，一定是$A [i]$比之前的都大；此时的$A[i]=B[i]$，是确定的
   对于不确定的$A[i]$，构造最大值时使其尽量大（$A[i] =B[i]$），构造最小值时使其尽量小（$A[i]=0$）
   构造和的最大值，只需要对数组$B$求和即可
   构造和的最小值，在$B[i]=B[i-1]$的时候将$A[i]$视作 $0$，$B[i]\ne B[i-1]$的时候将$A[i]$视作$B[i]$
   时间复杂度为$O(n)$
   代码

   #include<iostream>
   #include<cstdio>
   using namespace std;
   const int N=100+10;
   int n,maxSum,minSum;
   int b[N];
   int main(){
       scanf("%d",&n);
       for(int i=1;i<=n;i++){
           scanf("%d",&b[i]);
           if(b[i]!=b[i-1])
               minSum+=b[i];
           maxSum+=b[i];
       }
       printf("%d\n%d",maxSum,minSum);
       return 0;
   }

2. $100\%$数据
   在此基础上，由于当前的选择只与$B[i]$与$B[i-1]$有关，可以不使用数组，仅用两个变量记录；或使用滚动数组优化，以节省空间