C ++程序在旋转数组中查找给定长度的子数组的最大和查询

给定一个 N 整数数组 arr[] 和 Q 查询，两种类型为 {X, Y} ，具体如下：

如果 X = 1 ，则将给定数组向左旋转 Y 个位置。
如果 X = 2 ，则打印当前状态下长度为 Y 的最大和子数组。

示例：

输入： N = 5, arr[] = {1, 2, 3, 4, 5}, Q = 2, Query[][] = {{1, 2}, {2, 3}}

输出：

查询1：3 4 5 1 2

查询2：12

说明：

查询1：将数组向左移动2次：{1, 2, 3, 4, 5} -> {2, 3, 4, 5, 1} -> {3, 4, 5, 1, 2}

查询2：长度为3的最大和子数组是{3, 4, 5}，总和为12

输入： N = 5, arr[] = {3, 4, 5, 1, 2}, Q = 3, Query[][] = {{1, 3}, {1, 1}, {2, 4}}

输出：

查询1：1 2 3 4 5

查询2：2 3 4 5 1

查询3：14

说明：

查询1：将数组向左旋转3次：{3, 4, 5, 1, 2} -> {4, 5, 1, 2, 3} -> {5, 1, 2, 3, 4} -> {1, 2, 3, 4, 5}

查询2：将数组向左移动1次：{1, 2, 3, 4, 5} -> {2, 3, 4, 5, 1}

查询3：长度为4的最大和子数组是{2, 3, 4, 5}，总和为14

Naive方法： 最简单的方法是通过逐个移位对数组进行旋转，至于 X = 1 的查询，生成长度为 Y 的所有子数组的总和，如果查询是 X = 2 ，则打印最大总和。

时间复杂度： O（Q * N * Y）

辅助空间： O（N）

高效方法： 为了优化以上方法，可以使用Juggling算法来旋转数组，并使用滑动窗口技术查找长度为 Y 的最大和子数组。遵循以下步骤以解决该问题：

如果 X = 1 ，使用Juggling算法将数组向左旋转 Y 。
否则，如果 X = 2 ，使用滑动窗口技术找到长度为 Y 的最大和子数组。
如果查询 X 是 1 ，则打印数组。
否则，打印大小为 Y 的最大和子数组。

以下是上述方法的实现：

//上面的C++程序
  
#include 
using namespace std;
  
//计算长度为k的子数组最大和的函数。
int MaxSum(vector arr, int n, int k)
{
    int i, max_sum = 0, sum = 0;
   
    //计算前k个元素的最大和
    for (i = 0; i < k; i++) {
        sum += arr[i];
    }
    max_sum = sum;
   
    //查找最大和的子数组
    while (i < n) {
   
        //更新和
        sum = sum - arr[i - k] + arr[i];
        if (max_sum < sum) {
            max_sum = sum;
        }
        i++;
    }
   
    //返回最大和
    return max_sum;
}
  
//计算两个数字n1和n2的gcd的函数。
int gcd(int n1, int n2)
{
    //基本情况
    if (n2 == 0) {
        return n1;
    }
   
    //递归查找GCD
    else {
        return gcd(n2, n1 % n2);
    }
}
  
//旋转数组的函数，将数组旋转d步。
vector RotateArr(vector arr, int n, int d)
{
    //用于处理k> = N的情况。
    int i = 0, j = 0;
    d = d % n;
   
    //将数组分为多个集合。
    int no_of_sets = gcd(d, n);
   
    for (i = 0; i < no_of_sets; i++) {
   
        int temp = arr[i];
        j = i;
   
        //旋转数组
        while (true) {
   
            int k = j + d;
   
            if (k >= n)
                k = k - n;
   
            if (k == i)
                break;
   
            arr[j] = arr[k];
            j = k;
        }
   
        //更新arr[j]
        arr[j] = temp;
    }
   
    //返回旋转后的数组。
    return arr;
}
  
//在给定数组上执行查询的函数。
void performQuery(vector& arr, int Q[][2], int q)
{
   
    int N = (int)arr.size();
   
    //循环每个查询
    for (int i = 0; i < q; i++) {
   
        //如果查询类型为X = 1
        if (Q[i][0] == 1) {
   
            arr = RotateArr(arr, N, Q[i][1]);
   
            //打印数组
            for (auto t : arr) {
                cout << t << " ";
            }
            cout << "
";
        }
   
        //如果查询类型为X = 2
        else {
            cout << MaxSum(arr, N, Q[i][1])
                 << "
";
        }
    }
}
  
//驱动程序
int main()
{
    //给定数组arr[]
    vector arr = { 1, 2, 3, 4, 5 };
   
    int q = 5;
   
    //给定查询
    int Q[][2] = { { 1, 2 }, { 2, 3 }, 
                   { 1, 3 }, { 1, 1 }, 
                   { 2, 4 }
    };
   
    //函数调用
    performQuery(arr, Q, q);
   
    return 0;
}

输出: