当前位置:网站首页>golang力扣leetcode 396.旋转函数
golang力扣leetcode 396.旋转函数
2022-04-23 09:28:00 【cheems~】
396.旋转函数
题解
题目:给一个数组,计算f,f=下标*值 的累加,并且每次会把数组末尾的数移到前面,求最大的f
思路:
f(0)=0*nums[0]+1*nums[1]+2*nums[2]+...+(n-1)*nums[n-1]
f(1)=0*nums[n-1]+1*nums[0]+2*nums[1]+...+(n-1)*nums[n-2]
f(0)=0*nums[0]+1*nums[1]+2*nums[2]+...+(n-1)*nums[n-1]
f(1)=1*nums[0]+2*nums[1]+3*nums[2]+...+0*nums[n-1]
f(1)-f(0)=nums[0]+nums[1]+nums[2]-(n-1)*nums[n-1]
=nums[0]+nums[1]+nums[2]+nums[n-1]-n*nums[n-1]
设numSum=nums[0]+...+nums[n-1]
得f(1)-f(0)=numSum-n*nums[n-1]
得到通式f(i)-f(i-1)=numSum-n*nums[n-i]
f(i)=f(i-1)+numSum-n*nums[n-k]
代码
func maxRotateFunction(nums []int) int {
numSum, f, n := 0, 0, len(nums)
for i, v := range nums {
numSum += v
f += i * v
}
//numSum=nums[0]+...+nums[n-1]
//f(i)=f(i-1)+numSum-n*nums[n-i]
ans := f
for i := 1; i < len(nums); i++ {
f = f + numSum - n*nums[n-i]
ans = max(ans, f)
}
return ans
}
func max(i, j int) int {
if i > j {
return i
}
return j
}
版权声明
本文为[cheems~]所创,转载请带上原文链接,感谢
https://blog.csdn.net/qq_42956653/article/details/124341832
边栏推荐
- Group Backpack
- 小女孩行走
- Flink 流批一体在小米的实践
- Single sign on SSO
- Go language learning notes - language interface | go language from scratch
- Unfortunately, I broke the leader's confidential documents and spit blood to share the code skills of backup files
- 653. 两数之和 IV - 输入 BST
- Acquisition of DOM learning elements JS
- 653. Sum of two IV - input BST
- Two declaration methods of functions of JS
猜你喜欢
Production practice elk
Three challenges that a successful Devops leader should be aware of
JSON input of Chapter 14 of kettle paoding jieniu
Chapter VIII project stakeholder management of information system project manager summary
错题汇总1
[Luke V0] verification environment 2 - Verification Environment components
MySQL of database -- Fundamentals
成功的DevOps Leader 应该清楚的3个挑战
Kettle experiment
501. 二叉搜索树中的众数
随机推荐
《数字电子技术基础》3.1 门电路概述、3.2 半导体二极管门电路
Installation of data cleaning ETL tool kettle
JSON input of Chapter 14 of kettle paoding jieniu
MySQL of database -- basic common query commands
Using sqlmap injection to obtain the account and password of the website administrator
SAP 101K 411K 库存变化
The most concerned occupations after 00: civil servants ranked second. What was the first?
Thread scheduling (priority)
Little girl walking
Go language learning notes - array | go language from scratch
Leetcode0587. 安装栅栏(difficult)
STM32 and FreeRTOS stack parsing
Canary publishing using ingress
机器学习(六)——贝叶斯分类器
Kettle experiment conversion case
Common errors of VMware building es8
RSA 加密解密签名验签
Data visualization: use Excel to make radar chart
npm ERR! network
Chapter VIII project stakeholder management of information system project manager summary