396 旋转函数

给定一个长度为 n 的整数数组 A 。

假设 Bk 是数组 A 顺时针旋转 k 个位置后的数组，我们定义 A 的“旋转函数” F 为：F(k) = 0 * Bk[0] + 1 * Bk[1] + ... + (n-1) * Bk[n-1]。 计算F(0), F(1), ..., F(n-1)中的最大值。

注意: 可以认为 n 的值小于 105。

示例:

A = [4, 3, 2, 6]

F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25
F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) = 0 + 4 + 6 + 6 = 16
F(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3) = 0 + 6 + 8 + 9 = 23
F(3) = (0 * 3) + (1 * 2) + (2 * 6) + (3 * 4) = 0 + 2 + 12 + 12 = 26

所以 F(0), F(1), F(2), F(3) 中的最大值是 F(3) = 26 。

题解

1. 通过两次 for循环，在内层循环里，每遍历一次就修改原数组里数字的位置，这样就可以依次进行计算了。

TIP

执行用时：940 ms, 在所有 JavaScript 提交中击败了 36.36% 的用户
内存消耗：39.9 MB, 在所有 JavaScript 提交中击败了 34.78% 的用户

/**
 * @param {number[]} A
 * @return {number}
 */
var maxRotateFunction = function(A) {
    const {length: l} = A
    if(!l) return 0
    
    let max = -Infinity
    // 外层循环，控制次数
    for(let i=0;i<l;i++) {
        let compare = l-1
        let count = 0

        // 内层循环
        // 因为使用了数组的长度-1来进行乘法，所以就先从数组的末位向前加
         for(let j=l-1;j>0;j--) {
              // 计算总和
             count += A[j] * compare--
         }
         // 计算和之后，进行比较，保留最大值
         if(count > max) {
             max = count
         }
         // 修改原数组，这样每次遍历都是修改后的顺序
         A.push(A.shift())
    }

    return max
};

• 时间复杂度： `O(n^2)`，因为嵌套了两个 for循环。
• 空间复杂度： `O(1)`，使用了常数级别的空间
• 最好情况：
• 最坏情况：