【leetCode】396.旋转函数

import numpy as np
from typing import List
class Solution:
    def maxRotateFunction(self, nums: List[int]) -> int:
        length = len(nums)
        sum = []
        for i in range(0,length):
            count = 0
            s =0
            for j in range(length-i,length):
                s += count*nums[j]
                count+=1
            for j in range(0,length-i):
                s+=count*nums[j]
                count+=1
            sum.append(s)
        re = int(max(sum))
        return (re)


nums = [4,3,2,6]
a = Solution().maxRotateFunction(nums)
print(a)

但是一道中等难度的题想法自然不会那么简单。而且时间复杂度为0（n^2）
然后我想利用python中的矩阵乘法去试一下：但是这跟上面一样也是O（n^2）代码如下：

import numpy as np
from typing import List
class Solution:
    def maxRotateFunction(self, nums: List[int]) -> int:
        length = len(nums)
        temp = np.arange(0,length)
        temp = temp.tolist()
        ha = []
        ty = temp
        for i in range(0,length):
            ha.append(ty)
            ty = temp [length-i-1:]+temp[0:length-i-1]
        sum = np.dot(ha,nums)
        return max(sum)


nums = [4,3,2,6]
a = Solution().maxRotateFunction(nums)
print(a)

其实只要把前几种情况写出来，然后相邻两个方案对比一下，就可以找到规律：
如例子：【4，3,2,6】
04+13+22+36
06+14+23+32
看出来了吗 从4开始 比上一个多了一倍，但是最后一个数 是少了（n-1）倍。
这就是这道题的解法。

import numpy as np
from typing import List
class Solution:
    def maxRotateFunction(self, nums: List[int]) -> int:
        length = len(nums)
        result = []
        Sm = sum(nums)
        s = 0
        for i in range(0, length):
            s+=(i*nums[i])
        result.append(s)
        for i in range(0,length):
            s = result[-1] + Sm - nums[length-1-i] -nums[length-1-i]*(length-1)
            result.append(s)
        re = int(max(result))
        return (re)


nums = [4,3,2,6]
a = Solution().maxRotateFunction(nums)
print(a)