C++程序找出给定数组的所有旋转中i*arr[i]的最大和

给定一个由n个整数组成的数组arr []，找到最大化i * arr [i]值的总和的最大值，其中i从0到n-1变化。

示例：

输入： arr [] = {8, 3, 1, 2}
输出： 29
解释： 让我们看看所有的旋转，
{8, 3, 1, 2} = 8 * 0 + 3 * 1 + 1 * 2 + 2 * 3 = 11
{3, 1, 2, 8} = 3 * 0 + 1 * 1 + 2 * 2 + 8 * 3 = 29
{1, 2, 8, 3} = 1 * 0 + 2 * 1 + 8 * 2 + 3 * 3 = 27
{2, 8, 3, 1} = 2 * 0 + 8 * 1 + 3 * 2 + 1 * 3 = 17

输入：arr [] = {3, 2, 1}
输出：7
解释：让我们看看所有的旋转，
{3, 2, 1} = 3 * 0 + 2 * 1 + 1 * 2 = 4
{2, 1, 3} = 2 * 0 + 1 * 1 + 3 * 2 = 7
{1, 3, 2} = 1 * 0 + 3 * 1 + 2 * 2 = 7

Method 1 ： 该方法讨论了 Naive Solution ，需要O（n 2 ）的时间量。
解决方案涉及在每次旋转中找到数组所有元素的总和，然后决定最大总和值。

Approach: 一个简单的解决方案是尝试所有可能的旋转。计算每次旋转的i * arr [i]的求和并返回最大和。
Algorithm:
1. 旋转数组的所有值从0到n。
2. 计算每个旋转的总和。
3. 检查最大总和是否大于当前总和，然后更新最大总和。
Implementation:

// A Naive C++ program to find maximum sum rotation
#include<bits/stdc++.h>

using namespace std;

// Returns maximum value of i*arr[i]
int maxSum(int arr[], int n)
{
// Initialize result
int res = INT_MIN;

// Consider rotation beginning with i
// for all possible values of i.
for (int i=0; i<n; i++)
{

    // Initialize sum of current rotation
    int curr_sum = 0;

    // Compute sum of all values. We don't
    // actually rotate the array, instead of that we compute the
    // sum by finding indexes when arr[i] is
    // first element
    for (int j=0; j<n; j++)
    {
        int index = (i+j)%n;
        curr_sum += j*arr[index];
    }

    // Update result if required
    res = max(res, curr_sum);
}

return res;
}

// Driver code
int main()
{
    int arr[] = {8, 3, 1, 2};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << maxSum(arr, n) << endl;
    return 0;
}

输出：

复杂度分析：
时间复杂度： O（n 2 ），因为我们使用嵌套循环。

辅助空间： O（1），因为我们没有使用任何额外的空间。

Method 2： 该方法讨论了 efficient solution ，可以在O（n）的时间内解决问题。在Naive Solution中，对于每个旋转计算了值。因此，如果可以在恒定时间内完成，则复杂度将减少。

方法: 基本方法是计算前一个旋转到新旋转的总和。这带来了一个相似之处，在这里只有第一个和最后一个元素的乘数发生了巨大变化，每个其他元素的乘数增加或减少1。因此，可以从当前的旋转总和计算下一个旋转的总和。
算法:
想法是使用先前旋转的值来计算旋转的值。当数组旋转1个位置时，i*arr[i]的总和发生以下变化。
1. arr[i-1]的乘数从0变为n-1，即arr[i-1]*(n-1)添加到当前值中。
2. 其他项的乘数减少1.即从当前值中减去(cum_sum-arr[i-1])，其中cum_sum是所有数字的总和。

next_val = curr_val - (cum_sum - arr[i-1]) + arr[i-1] * (n-1);

next_val = 旋转后的∑i*arr[i]的值。
curr_val = 当前的值∑i*arr[i] 
cum_sum = 所有数组元素的总和，即∑arr[i]。

让我们以{1,2,3}为例。当前值为1*0+2*1+3*2=8。将其移位一个，将变为{2,3,1}，下一个值将为8-(6-1)+1*2=5，与2*0+3*1+1*2相同。

实现:

// 计算i*arr[i]的最大和的高效C++程序
# include<bits/stdc++.h>
 
using namespace std;
 
int maxSum(int arr[], int n)
{
    //计算所有数组元素的总和
    int cum_sum = 0;
    for (int i=0; i<n; i++)
        cum_sum += arr[i];
 
    //计算初始配置的i*arr[i]的总和
    int curr_val = 0;
    for (int i=0; i<n; i++)
        curr_val += i*arr[i];
 
    //初始化结果
    int res = curr_val;
 
    //计算其他迭代的值
    for (int i=1; i<n; i++)
    {
        // 使用先前的值计算下一个值
        int next_val = curr_val - (cum_sum - arr[i-1])
                       + arr[i-1] * (n-1);
 
        // 更新当前值
        curr_val = next_val;
 
        // 如有必要，则更新结果
        res = max(res, next_val);
    }
 
    return res;
}
 
// 测试代码
int main()
{
    int arr[] = {8, 3, 1, 2};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << maxSum(arr, n) << endl;
    return 0;
}

输出:

复杂度分析：
- 时间复杂度： O(n)。因为要从0到n循环一次以检查所有旋转，而当前旋转的和是从前几个旋转计算出来的，时间复杂度为 O(1)。
- 辅助空间： O(1)。因为不需要额外的空间，所以空间复杂度为 O(1) 。
方法： 假设数组是有序的。我们知道对于一个数组来说，当数组排序为升序时，最大和的数量是最大的。在旋转有序数组的情况下，我们可以旋转数组使其升序。所以，在这种情况下，需要找到中心点之后才能计算出最大和。
算法：
1. 查找数组的中心点： 如果 arr[i] > arr[(i+1)%n]，那么它就是中心点元素。 (i+1)%n 用于检查最后一个和第一个元素。
2. 在获取中心点之后，可以通过与中心点的差来计算和。以当前元素为乘数，计算和时乘以中心点的差
实现：
复杂度分析：
- 时间复杂度： O(n) 只需要一次从0到n的遍历来查找中心点。需要另一个循环来查找和，所以复杂度仍为 O(n) 。
- 辅助空间： O(1)。不需要额外的空间，所以辅助空间为 O(1) 。