forked from haoel/leetcode
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathRotateFunction.cpp
More file actions
75 lines (71 loc) · 2.17 KB
/
RotateFunction.cpp
File metadata and controls
75 lines (71 loc) · 2.17 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
// Source : https://leetcode.com/problems/rotate-function/
// Author : Hao Chen
// Date : 2016-11-03
/***************************************************************************************
*
* Given an array of integers A and let n to be its length.
*
* Assume Bk to be an array obtained by rotating the array A k positions clock-wise, we
* define a "rotation function" F on A as follow:
*
* F(k) = 0 * Bk[0] + 1 * Bk[1] + ... + (n-1) * Bk[n-1].
*
* Calculate the maximum value of F(0), F(1), ..., F(n-1).
*
* Note:
* n is guaranteed to be less than 105.
*
* Example:
*
* A = [4, 3, 2, 6]
*
* 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
*
* So the maximum value of F(0), F(1), F(2), F(3) is F(3) = 26.
***************************************************************************************/
//
// Asumming we have 4 numbers: a, b, c, d, then
// F(0) = 0a + 1b + 2c + 3d
// F(1) = 3a + 0b + 1c + 2d
// F(2) = 2a + 3b + 0c + 1d
// F(3) = 1a + 2b + 3c + 0d
//
// We can see how F(n) transfrom to F(n+1)
// F(0) - F(1) = -3a + b + c + d
// F(1) - F(2) = a + -3b + c + d
// F(2) - F(3) = a + b + -3c + d
// F(3) - F(0) = a + b + c + -3d
//
// So, we can tansfrom to the following experssion:
//
// F(1) = F(0) - (a+b+c+d) + 4a
// F(2) = F[1] - (a+b+c+d) + 4b
// F(3) = F[2] - (a+b+c+d) + 4c
//
// Then, we can see this fomular:
//
// F(n) = F(n-1) - sum(array) + len(array) * array[n-1]
//
class Solution {
public:
int maxRotateFunction(vector<int>& A) {
int sum = 0;
int F = 0;
for (int i=0; i < A.size(); i++) {
sum += A[i];
F += (i * A[i]);
}
int maxF = F;
int len = A.size();
//cout << "F(0) = " << maxF <<endl;
for (int i=1; i< len; i++) {
F = F - sum + len * A[i-1];
//cout << "F(" << i << ") = " << F << endl;
maxF = max(maxF, F);
}
return maxF;
}
};