️ Personal home page ： loaf on a job の Wenjiang blog home page ‍*️
The blogosphere ：java Programming based ,mysql
Writing style ： dried food , dried food , still tmd Dry goods of
Select columns ：【Java】【mysql】 【 Algorithm brush problem note 】
Blogger's code cloud gitee, Usually the program code written by bloggers is inside .
Support bloggers ： give the thumbs-up 、 Collection 、 Leaving a message.
The author's level is very limited , If an error is found , Be sure to inform the author in time ！ Thank you thank you ！

Rotated array

1. Original link

Rotated array

2. Subject requirements

   Given a length of n Array of integers for nums .
hypothesis arrk It's an array nums Clockwise rotation k Array after position , We define nums Of Rotation function F by ：

$$F(k)=0\ast arrk[0]+1\ast arrk[1]+...+(n-1)\ast arrk[n-1]$$

return F(0), F(1), …, F(n-1) Maximum of .
The generated test cases make the answers meet the requirements 32 position Integers .

   The sample input : nums = [4,3,2,6]

   Sample output : 26

   explain :
  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
   therefore F(0), F(1), F(2), F(3) The maximum value in is F(3) = 26 .

3. Basic framework

java The basic framework code of version is as follows :

class Solution {
    
    public int maxRotateFunction(int[] nums) {
    

    }
}

4. Their thinking

  1. According to the rotation of the array, we can think of nums Copy splice
  2. Then from the first to the n-1 Take turns at the beginning to execute the formula . Get the maximum prefix and

5. Complete code

class Solution {
    // Sliding window prefixes and 
        public int maxRotateFunction(int[] nums) {
    
            int n = nums.length;
            int[] sum = new int[n * 2 + 10];
            for (int i = 1; i <= 2 * n; i++) sum[i] = sum[i - 1] + nums[(i - 1) % n];
            int ans = 0;
            for (int i = 1; i <= n; i++) ans += nums[i - 1] * (i - 1);
            for (int i = n + 1, cur = ans; i < 2 * n; i++) {
    
                cur += nums[(i - 1) % n] * (n - 1);
                cur -= sum[i - 1] - sum[i - n];
                if (cur > ans) ans = cur;
            }
            return ans;
        }
    }

6. It's about algorithms & summary

The sliding window The prefix and