[数据结构与算法]leetcode396

题目

暴力Time Out

//两次遍历会Time Out
    public static int maxRotateFunction(int[] nums) {
        //模拟循环链表
        int length = nums.length;
        int max = Integer.MIN_VALUE;
        for (int i = length; i > 0; i--) {
            int index = i;
            int cur = 0;
            for (int j = 0; j < length; j++) {
                cur += nums[index % length] * j;
                index++;
            }
            max = Math.max(cur, max);
        }
        return max;
    }

数组这类问题可以找规律

记数组nums 的元素之和为numSum。根据公式，可以得到：
F(0)=0×nums[0]+1×nums[1]+…+(n?1)×nums[n?1]
F(1)=1×nums[0]+2×nums[1]+…+0×nums[n?1]=F(0)+numSum?n×nums[n?1]
更一般地，当 1≤k<n 时，F(k)=F(k?1)+numSum?n×nums[n?k]。我们可以不停迭代计算出不同的 F(k)，并求出最大值

class Solution {
        public int maxRotateFunction(int[] nums) {
            int length = nums.length;
            int sum = 0;
            int f = 0;
            for (int i = 0; i < length; i++) {
                sum += nums[i];
                f += i * nums[i];
            }
            int res = f;
            for (int i = length - 1; i > 0; i--) {
                f = sum + f - length * nums[i];
                res = Math.max(res, f);
            }
            return res;
        }
    }

总结，数组类型，可以利用到前缀和，找规律，滑动窗口，双指针。

阅读世界，共赴山海

423全民读书节，邀你共读