Next Quiz

解析：完善程序-2

信息学奥赛历年真题 2023年CSP提高组真题解析：完善程序-2

问题描述

这道题目的核心任务是：给定一个长度为n的数组a，求出所有子数组的最大值之和。

算法思路

分治法： 将原数组递归地分成左右两部分，分别求解左右两部分的最大值之和。
跨越中点的子数组： 对于跨越中点的子数组，采用双指针和前缀和的技巧进行优化。
前缀最大值： 对于右半部分，预处理出每个位置的前缀最大值，以便快速计算跨越中点的子数组的最大值。

代码详解

solve(l, r)函数：
- 递归基： 当区间长度为1时，直接将元素加入答案。
- 分治： 递归求解左右两部分。
- 跨越中点的子数组：
  - 复制右半部分： 将右半部分复制到pre数组中，并计算每个位置的前缀最大值。
  - 前缀和： 计算pre数组的前缀和，存储在sum数组中。
  - 双指针： 使用两个指针i和j分别从左半部分的末尾和右半部分的开头开始遍历。
  - 更新最大值： 维护一个max变量，记录当前左半部分的最大值。
  - 计算贡献： 对于每个左半部分的元素a[i]，找到右半部分中第一个不小于a[i]的元素a[j]。
    - (j - mid) * max：表示以a[i]为左端点，在右半部分能扩展到的子数组个数乘以最大值。
    - sum[r - mid] - sum[j - mid]：表示右半部分从j到r-1这一段的最大值之和。
主函数：
- 输入数组。
- 调用solve函数，计算并输出答案。

算法复杂度

时间复杂度： O(nlogn)，由于分治的递归树深度为logn，每一层遍历数组一次，故总时间复杂度为O(nlogn)。
空间复杂度： O(n)，主要用于存储额外的数组pre和sum。

优化点

空间优化： 可以通过滚动数组的方式，减少额外的空间开销。
代码优化： 可以对一些细节进行优化，例如减少不必要的赋值操作。

总结

该代码通过分治、双指针和前缀和的巧妙结合，高效地解决了求所有子数组最大值之和的问题。算法的时间复杂度和空间复杂度都比较优秀。

需要注意的是：

左闭右开区间： 函数solve处理的是左闭右开的区间，即[l, r)。
前缀最大值： pre数组存储的是从pre[0]到pre[i]的最大值，而不是从a[mid]到a[i]的最大值。
前缀和： sum数组存储的是pre数组的前缀和。

代码实现：

/**************************************************************** 
 * Description: 2023_CSP_S  完善程序-2
 * Author: Alex Li
 * Date: 2024-06-19 09:27:04
 * LastEditTime: 2024-06-19 22:50:42
****************************************************************/
#include <iostream>
#include <algorithm>
#include <vector>

const int MAXN=100000;

int n;
int a[MAXN];
long long ans;

void solve(int l, int r){
    if(l+1==r){
        ans+=a[l];  //左闭右开的区间，a[0]~a[r-1]
        return ;
    }
    int mid=(l+r)>>1;
    std::vector<int> pre(a+mid, a+r);   //复制数组a[mid]~a[r-1]到pre
    //经过这个循环，pre[i]存储的是从pre[0]到pre[i]的最大值。
    for(int i=1; i<r-mid;++i) pre[i]=std::max(pre[i],pre[i-1]);
    std::vector<long long> sum(r-mid+1); 
    for(int i=0;i<r-mid;++i) 
        sum[i+1]=sum[i]+pre[i];   //前缀最大值之和
    /*i：从mid - 1（左半部分的最后一个元素）开始，向左遍历到1。
    j：从mid（右半部分的第一个元素）开始，向右遍历到r。
    max：用于记录遍历过程中左半部分的最大值。
    这段代码的目的是通过遍历左半部分，结合右半部分的信息，计算所有跨越中点的子数组的最大值之和。
    通过调整指针j，确定每个左半部分的元素a[i]在右半部分能扩展到的位置，并且结合前缀最大值和前缀和，
    快速计算并累加这些子数组的最大值之和。
    */
    for(int i=mid-1,j=mid,max=0;i>=l;--i){
        //这个循环将j指针向右移动，直到找到第一个不小于a[i]的元素或者到达右半部分的末尾r。
        //目的：找到右半部分中第一个不小于a[i]的元素，从而确定a[i]在右半部分能扩展到的位置。
        while(j<r&&a[j]<a[i])++j;
        max=std::max(max,a[i]); //更新最大值
        //计算并累加左半部分当前元素a[i]能扩展到右半部分的位置数（j - mid），乘以当前的最大值max。
        //(j - mid)表示从mid到j-1这一段元素的数量。
        //max是当前左半部分的最大值。
        ans+=(long long)(j-mid)*max;
        /*使用右半部分的前缀和数组sum，累加从j到r-1这一段的最大值之和。
          sum[r - mid]表示右半部分所有元素的最大值之和。
          sum[j - mid]表示从mid到j-1这一段元素的最大值之和。
           因此，sum[r - mid] - sum[j - mid]表示从j到r-1这一段元素的最大值之和。
        */
        ans+=sum[r-mid]-sum[j-mid];
    }
    solve(l,mid);
    solve(mid,r);
}

int main(){
    std::cin>>n;
    for(int i=0;i<n;++i)
        std::cin>>a[i];
    solve(0,n); //左闭右开的区间
    std::cout<<ans<<std::endl;
    return 0;
}

Previous Topic

Back to Lesson

Next Quiz