In this Leetcode Rotate Function problem solution you are given an integer array nums of length n. Assume arrk to be an array obtained by rotating nums by k positions clock-wise. We define the rotation function F on nums as follow:
F(k) = 0 * arrk[0] + 1 * arrk[1] + ... + (n - 1) * arrk[n - 1].
Return the maximum value of F(0), F(1), ..., F(n-1). The test cases are generated so that the answer fits in a 32-bit integer.
Problem solution in Python.
class Solution: def maxRotateFunction(self, A: List[int]) -> int: list_len = len(A) # edge cases if list_len <= 1: return 0 l_sum = 0 l_times_n = [0] * list_len orig_sum = 0 for i in range(list_len): val = A[i] l_sum += val l_times_n[i] = val*list_len orig_sum += val * i max_sum = orig_sum for i in range(list_len-1): orig_sum = orig_sum - l_sum + l_times_n[i] if orig_sum >= max_sum: max_sum = orig_sum return max_sum
Problem solution in Java.
public class Solution { public int maxRotateFunction(int[] A) { int F = 0; int Asum = 0; int count = A.length; for (int i=0;i<count;i++){ F+=A[i]*i; Asum+=A[i]; } int max=F; for (int j=1;j<count;j++){ F=F+Asum-A[count-j]*count; max=Math.max(max,F); } return max; } }
Problem solution in C++.
class Solution { public: int maxRotateFunction(vector& nums) { int n=nums.size(); int csum=0,m_sum=INT_MIN; int sum=accumulate(nums.begin(),nums.end(),0); for(int i=0;i<n;i++) csum+=(i*nums[i]); m_sum=max(csum,m_sum); for(int i=1;i<n;i++) { int t_sum=(csum-(nums[n-i]*(n-1)))+(sum-nums[n-i]); csum=t_sum; m_sum=max(csum,m_sum); } return m_sum!=INT_MIN?m_sum:0; } };
Problem solution in C.
int maxRotateFunction(int* A, int ASize) { int i, last, sum,m; if(ASize<=1) return 0; last=0; sum=0; for(i=0;i<ASize;i++){ last += A[i]*i; sum+=A[i]; } m=last ; for(i=ASize-1;i>=1;i--){ last += sum - (ASize*A[i]); if (last > m) m= last; } return m; }
0 Comments