C++ 使得元素可以通过最大K递增相等的最长子数组

在这个问题中，我们需要找到最长子数组的长度，以便通过添加一些正整数值使所有子数组元素相同，并且每个元素的添加数字的总和不应超过K。

朴素的方法是找出使给定数组中的所有元素相同的成本。最后，考虑成本小于K且长度最大的子数组的长度。

然而，我们将使用队列数据结构高效地解决这个问题。

问题描述 − 给定一个包含整数的大小为N的数组。还给出一个正整数K。任务是找到最长子数组的长度，以便通过向子数组的每个元素添加一些数字来使子数组的所有元素都相等。同时，添加数字的总和应不超过K。

示例

输入

K = 6; arr[] = {2, 3, 5, 15, 3, 8};

输出

3

解释 −我们可以取子数组{2,3,5}。所以，使子数组中所有元素相等的总费用是{3,2,0}的和，即5。

输入

K = 2; arr[] = {2, 2, 2, 2, 2, 2}

输出

6

解释 − 给定数组的所有元素都相同。因此，我们可以将给定的数组选择为子数组。

输入

K = 3; arr[] = {4, 5, 4, 4, 5, 1, 2, 3, 3, 3};

输出

5

解释 - 在这里，我们可以选择{4, 5, 4, 4, 5}或者{1, 2, 3, 3, 3}子数组，因为这两个数组的长度相同，将所有数字都变为3的成本相等。

方法1

在这个方法中，我们将遍历给定数组的所有子数组。同时，我们将跟踪当前子数组的最大元素和元素的总和。如果将子数组的所有元素都变为相等的成本小于K，并且其长度小于max_len，则更新max_len。

步骤

步骤1 - 定义max_len并初始化为0。

步骤2 - 使用循环遍历数组。在循环中，定义maxEle和sum变量，并将它们初始化为0。

步骤3 - 使用另一个嵌套循环从第P个索引开始遍历数组，因为子数组从第P个索引开始。

步骤4 - 如果当前数组元素小于maxEle，则更新maxEle。同时，将数组元素添加到sum变量中。

步骤5 - 现在，我们需要将子数组的所有元素都变为maxEle，并且子数组的长度为q – p + 1。因此，如果maxEle * (q – p + 1)小于或等于K，则如果max_len小于q – p + 1，则更新max_len变量。

步骤6 - 返回max_len的值。

示例

#include <bits/stdc++.h>
using namespace std;

int maxSubArrayLength(int arr[], int N, int K) {
    int max_len = 0;
    // Traverse all subarrays of the given array
    for (int p = 0; p < N; p++) {
        int maxEle = 0;
        int sum = 0;
        for (int q = p; q < N; q++) {
            // Update maximum element
            maxEle = max(maxEle, arr[q]);
            sum += arr[q];
            // Check whether we can make all elements of the array equal to maxEle
            if (maxEle * (q - p + 1) <= sum + K) {
                // Update maximum length
                max_len = max(max_len, q - p + 1);
            }
        }
    }
    return max_len;
}
int main() { 
    int N = 6;
    int K = 6;
    int arr[] = {2, 3, 5, 15, 3, 8};
    cout << "The maximum length of subarray such that we can make all elements of it same is " << maxSubArrayLength(arr, N, K);
    return 0;
}

输出

The maximum length of subarray such that we can make all elements of it same is 3

时间复杂度 – O(N*N) 遍历所有子数组。

空间复杂度 – O(1)

方法2

步骤

步骤 1 − 定义名为’maxQueue’的双端队列数据结构，用于存储子数组中最大元素的索引。

步骤 2 − 定义pref_sum[] 数组来存储前缀和，并将0号索引初始化为0。

步骤 3 − 遍历数组，并将元素的前缀和存储到pref_sum[]数组中。

步骤 4 − 将’left’和’max_len’初始化为0，分别指向数组的左索引和跟踪子数组最大长度的变量。同时，定义max_ele来存储子数组的最大元素。

步骤 5 − 再次遍历数组。

步骤 5.1 − 在for循环中，使用while循环从队列中移除元素，直到队列为空或者队列的最后一个元素小于arr[p]。

步骤 5.2 − 将 p 插入队列。

步骤 5.3 − 如果 p 为0，将max_ele初始化为arr[p]。否则，仅当max_ele小于arr[p]时更新max_ele。

步骤 5.4 − 使用while循环迭代，直到(p – left + 1) * max_ele – (pref_sum[p + 1] – pref_sum[left])大于K，或者’left’小于p。

步骤 5.4.1 − 在while循环中，每次迭代将’left’增加1。

步骤 5.4.2 − 同时，从队列中移除小于’left’的元素。

步骤 5.5 − 如果p – left + 1大于max_len，则将max_len更新为p – left + 1。

步骤 6 − 返回max_len的值。

示例

#include <bits/stdc++.h>
using namespace std;

int maxSubArrayLength(int arr[], int N, int K) {
    // Queue to store elements
    deque<int> maxQueue;
    // To store prefix sum
    int pref_sum[N + 1];
    pref_sum[0] = 0;
    // Calculating the prefix sum
    for (int p = 1; p <= N; p++) {
        pref_sum[p] = pref_sum[p - 1] + arr[p - 1];
    }
    // Start point of sub-array
    int left = 0;
    // For tracking the maximum element of the sub-array
    int max_ele;
    // To store the answer
    int max_len = 0;
    for (int p = 0; p < N; p++) {
        // Remove all smaller elements from the back to make the current element as maximum
        while (!maxQueue.empty() && arr[maxQueue.back()] < arr[p]) {
            maxQueue.pop_back();
        }
        // Insert current index
        maxQueue.push_back(p);
        // Update maximum element
        if (p == 0) {
            max_ele = arr[p];
        } else 
            max_ele = max(max_ele, arr[p]);
        // Calculating the cost to make all elements equal to the maximum
        while ((p - left + 1) * max_ele - (pref_sum[p + 1] - pref_sum[left]) > K && p > left) {
            // Increment starting point
            left++;
            // Remove the element from the current window
            while (!maxQueue.empty() && maxQueue.front() < left && left < p) {
                maxQueue.pop_front();
                max_ele = arr[maxQueue.front()];
            }
        }
        // Update maximum size
        max_len = max(max_len, p - left + 1);
    }
    return max_len;
}
int main() {
    int N = 6;
    int K = 6;
    int arr[] = {2, 3, 5, 15, 3, 8};
    cout << "The maximum length of subarray such that we can make all elements of it same is " << maxSubArrayLength(arr, N, K);
    return 0;
}

输出

The maximum length of subarray such that we can make all elements of it same is 3

时间复杂度 − O(N^2)，因为我们使用了嵌套循环。

空间复杂度 − O(N)，因为我们使用了队列。

在最坏的情况下，这两种方法具有相同的时间复杂度。然而，当我们需要在常规数组中执行给定操作时，第二种方法更加有效。