C++ 序列权值最大最小值算法：求解最大和最小权值

Lee拿到一个长度为n的序列a，他可以通过序列a(a0,a1,...an-1)得到一个权值w，其中 w=a0a1+a1a2+...+an-2*an-1，现在Lee可以选择一个ai,i属于[1,n-1]，使得ai的值变为ai-1的值，从而获取得到一个权值w。

现在请问最多经过一次上述的操作后，最大能得到的w与最小能得到的w。

输入

第一行一个整数t，代表有t组数据，对于每组数据：第一行一个整数n,代表序列a的长度。第二行n个整数，代表序列a。

数据范围

1<=t<=1000,1<=n<=1000,1<=ai<=1000,所有数据n之和小于等于10^6

输出格式

每组数据一行，两个整数，代表最小能得到的w与最大能得到的w

样例输入

2 5 1 2 3 4 5 3 3 2 1

样例输出

32 40 8 12

C++ 代码实现

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    int t;
    std::cin >> t;

    while (t--) {
        int n;
        std::cin >> n;

        std::vector<int> a(n);
        for (int i = 0; i < n; i++) {
            std::cin >> a[i];
        }

        int minW = a[0] * a[1]; // 初始最小权值
        int maxW = a[0] * a[1]; // 初始最大权值

        for (int i = 1; i < n - 1; i++) {
            int currW = a[i] * a[i+1];
            minW = std::min(minW, currW);
            maxW = std::max(maxW, currW);
        }

        std::cout << minW << ' ' << maxW << std::endl;
    }

    return 0;
}

代码解释

首先读取t，表示有t组数据。
对于每组数据，首先读取n，表示序列a的长度。
然后读取n个整数，表示序列a。
初始化最小权值minW和最大权值maxW为序列中第一个元素和第二个元素相乘的结果。
遍历序列a的第2个元素到倒数第2个元素，计算当前元素和下一个元素相乘的结果currW。
如果currW比minW小，则更新minW为currW。
如果currW比maxW大，则更新maxW为currW。
输出最小权值minW和最大权值maxW。