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

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 的最大和子数组。遵循以下步骤以解决该问题:

  1. 如果 X = 1 ,使用Juggling算法将数组向左旋转 Y
  2. 否则,如果 X = 2 ,使用滑动窗口技术找到长度为 Y 的最大和子数组。
  3. 如果查询 X1 ,则打印数组。
  4. 否则,打印大小为 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;
}  

输出:

3 4 5 1 2 
12
1 2 3 4 5 
2 3 4 5 1 
14

时间复杂度: O(Q*N),其中Q是查询数 , 而N是给定数组的大小。

辅助空间: O(N)

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程

C++ 示例