题解

题目描述

给定一个长度为 $n$ 的数组 ${a_1,a_2,\dots,a_n}$，需要将数组分成两部分：前缀部分 ${a_1,a_2,\dots,a_x}$ 和后缀部分 ${a_{x+1},a_{x+2},\dots,a_{n}}$（其中 $1 \le x < n$），使得下式达到最大值：

$sum_{i=1}^{x} \sum_{j=x+1}^{n} a_i \times a_j$

注意：输出结果需对$998244353$ 取模。

思路分析

题目要求求解以下表达式的最大值：

令 $S$ 为数组所有元素之和，即

$S=sum_{i=1}^{n} a_i$

当我们确定了分割位置 $x$ 后：

• 前缀部分之和为 $text{pre}=sum_{i=1}^{x} a_i$，
• 后缀部分之和为 $S-\text{pre}$。

于是表达式可以转化为

$P(x)= text{pre} \times (S-\text{pre})$

由于数组中的每个$a_i$均为正数，该式为一个关于$\text{pre}$的二次函数：

该二次函数开口向下，在理论上当$text{pre}=S/2$ 时达到最大值，但由于题目要求分割位置为连续的整数位置，所以我们只需要遍历每个可能的分割位置$x (1\le x<n)$，计算对应的$P(x)$，并取其中的最大值，最后再对$998244353$取模即可。

C++

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
const ll MOD = 998244353;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    vector<int> a(n);
    // 读取数组
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    
    // 计算数组所有元素之和 S
    ll S = 0;
    for(int i = 0; i < n; i++){
        S += a[i];
    }
    
    ll prefix = 0;
    ll ans = 0;
    // 枚举分割位置 x，x 的取值范围为 1 到 n-1
    for(int x = 0; x < n - 1; x++){
        prefix += a[x];         // 前缀和 pre = ∑(a[0]..a[x])
        ll suffix = S - prefix;   // 后缀和 = S - pre
        ll product = prefix * suffix;  // 计算表达式值
        if(product > ans)
            ans = product;
    }
    
    // 输出答案，对 MOD 取模
    cout << ans % MOD << "\n";
    return 0;
}

Python

# 定义 MOD 值
MOD = 998244353

# 读取输入
n = int(input())
a = list(map(int, input().split()))

# 计算数组所有元素之和 S
S = sum(a)

prefix = 0
ans = 0

# 枚举分割位置，位置从 0 到 n-2（对应题目中的 1 到 n-1）
for i in range(n - 1):
    prefix += a[i]        # 累加前缀和
    suffix = S - prefix   # 后缀和
    product = prefix * suffix  # 计算表达式值
    if product > ans:
        ans = product

# 输出答案，对 MOD 取模
print(ans % MOD)

Java

import java.util.Scanner;

public class Main {
    // 定义 MOD 值
    public static final long MOD = 998244353;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取数组大小 n
        int n = scanner.nextInt();
        int[] a = new int[n];
        
        // 读取数组元素
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }
        
        // 计算数组所有元素之和 S
        long S = 0;
        for (int i = 0; i < n; i++) {
            S += a[i];
        }
        
        long prefix = 0;
        long ans = 0;
        // 枚举分割位置，从 0 到 n-2 对应题目的分割位置 1 到 n-1
        for (int i = 0; i < n - 1; i++) {
            prefix += a[i];           // 更新前缀和
            long suffix = S - prefix;   // 计算后缀和
            long product = prefix * suffix;  // 计算表达式值
            if (product > ans) {
                ans = product;  // 更新最大值
            }
        }
        
        // 输出答案，对 MOD 取模
        System.out.println(ans % MOD);
        scanner.close();
    }
}

题目内容

$Tk$有一个长度为$n$的数组{$a_1,a_2,...,a_n$}，他希望将数组分割为{$a_1,a_2,...,a_x$}和{$a_{x+1},a_{x+2},a_n$}两个部分(显然，$x$需要满足$1 ≦x<n$)，使得下式的答案达到最大:

$\sum^x_{i=1}\sum^n_{j=x+1}a_i×a_j$

这却难倒聪明的他了，现在他来寻求你的帮助，不过你并不需要告诉他具体分割位置，只需要告诉他最终结果即可。由于答案可能很大，请将答案对 $998\ 244\ 353$取模后输出。

输入描述

第一行输入一个正整数$n(2≦n≦2×10^5)$表示数组大小。

第二行输入$n$个整数$a_1,a_2,...,a_n (1≦a≦10^4)$代表数组中的元素。

输出描述

输出一个值表示上式的最大值。由于答案可能很大，请将答案对$998\ 244\ 353$取模后输出。

样例1

输入

5
3 2 4 1 5

输出

54

说明

分割最终区间为$[1,3],[4,5]$,可以得到最大值$54$