C++程序仅允许旋转给定数组，找到Sum( i*arr[i])的最大值

给定一个数组，仅允许对数组进行旋转操作。我们可以旋转数组任意次。返回i* arr[i] 的最大可能总和。

示例：

输入：arr[] = {1, 20, 2, 10}
输出：72
我们可以通过旋转数组两次来得到72。
{2, 10, 1, 20}
20 * 3 + 1 * 2 + 10 * 1 + 2 * 0 = 72

输入：arr[] = {10, 1, 2, 3, 4, 5, 6, 7, 8, 9}
输出：330
我们可以通过旋转数组9次来得到330。
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
0 * 1 + 1 * 2 + 2 * 3 … 9 * 10 = 330

我们强烈建议您最小化浏览器并首先尝试此操作。

一个 简单的解决方案 是一个一个找出所有旋转，检查每个旋转的总和并返回最大总和。此解决方案的时间复杂度为O(n 2 )。

我们可以使用一个 高效的解决方案 在O(n) 时间内解决这个问题。

设R j 为i* arr [i]值与j旋转的值。这个想法是从以前的旋转计算下一个旋转的值，即从R j-1 计算R j 。我们可以将结果的初始值计算为R 0 ，然后继续计算下一个旋转值。

**如何有效地计算从R j-1 到R j ? **

这可以在O(1)时间内完成。以下是详细信息。

让我们计算没有旋转的i* arr [i]的初始值
R0 = 0 * arr [0] + 1 * arr [1] +…+ (n-1) * arr [n-1]

1个旋转后，arr [n-1] 成为数组的第一个元素，
arr [0] 成为第二个元素，arr [1] 成为第三个元素，
依此类推。
R1 = 0 * arr [n-1] + 1 * arr [0] +…+ (n-1) * arr [n-2]

R1 – R0 = arr [0] + arr [1] + … + arr [n-2] – (n-1) * arr [n-1]

2次旋转后，arr [n-2] 成为数组的第一个元素，
arr [n-1] 成为第二个元素，arr [0] 成为第三个元素，
依此类推。
R2 = 0 * arr [n-2] + 1 * arr [n-1] +…+ (n-1) * arr [n-3]

R2 – R1 = arr [0] + arr [1] + … + arr [n-3] – (n-1) * arr [n-2] + arr [n-1]

如果我们仔细观察上述值，我们可以观察到下面的模式

Rj – Rj-1 = arrSum – n * arr [n-j]

其中arrSum是所有数组元素的总和，即，

arrSum = ∑ arr [i]
0 <= i <= n-1

以下是完整算法：

1）计算所有数组元素的总和。让这个总和为’arrSum’。

2）通过对给定数组进行i* arr [i]计算来计算R0。
让这个值为currVal。

3）初始化结果：maxVal = currVal // maxVal是结果。

//这个循环从Rj-1计算Rj
4）对j = 1 至 n-1 执行以下操作
……a）currVal = currVal + arrSum-n * arr [n-j];
……b）如果 (currVal> maxVal)
maxVal = currVal

5）返回maxVal

以下是以上思路的实现：

// C++程序查找i* arr[i]的最大值
#include
using namespace std;

// 返回i* arr [i]的最大可能值
int maxSum（int arr []，int n）
{
    //查找没有旋转的数组和i∗arr [i]
    int arrSum = 0; //存储arr [i]的总和
    int currVal = 0; //存储i∗arr [i]的总和
    for（int i = 0; i  maxVal）
            maxVal = currVal;
    }

    //返回结果
    return maxVal;
}

//驱动程序
int main（void）
{
    int arr [] = {10,1,2,3,4,5,6,7,8,9};
    int n = sizeof（arr）/ sizeof（arr [0]）;
    cout <<“
最大和为”<< maxSum（arr，n）;
    return 0;
} ```

输出：