极客笔记C++程序 找出给定数组的所有旋转中i*arr[i]的最大和
问题描述
给定一个包含n个整数的数组arr，每个整数都不相同。找到一个旋转数组的索引点，这个旋转数组是由原数组旋转k个元素而来，k是未知的。旋转数组的定义是，将数组的最后k个元素放到前面去，并将剩余的元素向后移动k个位置。比如，如果一个数组原来是[1,2,3,4,5,6]，那么它的旋转数组可能是[5,6,1,2,3,4]或者[6,1,2,3,4,5]等等。
我们定义一个数组的旋转中心为i，数组的旋转值为i*arr[i]。给定一个数组，求出所有旋转中心的值中，最大的一个。
例如：
给定数组：[8,3,1,2,7,5,6,4]
我们可以把他成旋转的形式：
[8,3,1,2,7,5,6,4] => [1,2,7,5,6,4,8,3]
旋转中心i为0时，旋转值为0
旋转中心i为1时，旋转值为1×2=2
旋转中心i为2时，旋转值为2×7=14
旋转中心i为3时，旋转值为3×5=15
旋转中心i为4时，旋转值为4×6=24
旋转中心i为5时，旋转值为5×4=20
旋转中心i为6时，旋转值为6×8=48
旋转中心i为7时，旋转值为7×3=21
最大的旋转值为48，因此答案为48。
提示： n<=1000，保证数组中的每一个数都在[1, 10^6]范围内
思路分析
对于这个问题，我们需要依次求出数组的每一个旋转点为i时，旋转值i*arr[i]的大小。那么，如何求出这个旋转值呢？
对于旋转点i，我们可以把原数组拆成两个数组arr1[0~i-1]和arr2[i~n-1]，这样我们就可以将原数组旋转成arr2+arr1的形式，即：arr[i~n-1]+arr[0~i-1]。
因为旋转点之后的元素与旋转点之前的元素顺序翻转了过来，因此对于任意一个位置j，它在旋转后的位置为(j-i+n)%n，因此，
所以旋转后的数组为arr[(j-i+n)%n]
旋转值为i*arr[(j-i+n)%n]
对于每一个旋转点，我们只需要依次求出i*arr[(j-i+n)%n]的和即可，最后取其中的最大值作为结果。
完整代码
#include<iostream>
using namespace std;
int findMax(int arr[], int n){
int max_sum = INT_MIN;
for (int i = 0; i < n; i++){
int sum = 0;
for (int j = 0; j < n; j++){
sum += j * arr[(j - i + n) % n];
}
if (sum > max_sum){
max_sum = sum;
}
}
return max_sum;
}
int main(){
int arr[] = {8,3,1,2,7,5,6,4};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Max sum is: " << findMax(arr, n) << endl;
return 0;
}
结论
通过上面的代码，我们可以轻松地找出给定数组的所有旋转中i*arr[i]的最大和。这个算法的时间复杂度为O(n^2)，因为它需要嵌套两个循环来计算每个旋转点的旋转值。然而，由于这个问题的规模不大，这个算法的速度还是可以接受的。
除了这个暴力枚举的方法，还有一种更高效的解法。这个解法的思路是，首先计算出原数组的总和sum，以及0到n-1的和indexes_sum。然后从0到n-1枚举每个旋转点，计算旋转值，同时更新最大值。具体实现可参考下面的代码：
int findMax(int arr[], int n){
int sum = 0;
int indexes_sum = 0;
for (int i = 0; i < n; i++){
sum += arr[i];
indexes_sum += i * arr[i];
}
int max_sum = indexes_sum;
for (int i = 1; i < n; i++){
indexes_sum = indexes_sum + sum - n * arr[n-i];
if (indexes_sum > max_sum){
max_sum = indexes_sum;
}
}
return max_sum;
}
这个算法的时间复杂度为O(n)，相比暴力枚举的方法快了很多。但需要注意的是，这个方法只适用于数组元素不重复的情况，如果数组元素有重复，则需要考虑如何处理重复元素的位置。
总之，这个问题的解法还是比较简单的，只要对每个旋转点依次计算旋转值即可。如果需要更高效的解法，则可以使用上面提到的方法。