## Saturday, October 8, 2016

### LeetCode OJ - Rotate Function

Problem:

Analysis:

The key idea for this problem is that once we evaluated $F(0)$, we can quickly evaluate $F(1)$ as follow:

$F(0) = 0 a[0] + 1 a[1] + 2 a[2] + 3 a[3]$

$F(1) = 0 a[1] + 1 a[2] + 2 a[3] + 3 a[0]$

Rearranging, we get:

$F(0) = 0 a[0] + 1 a[1] + 2 a[2] + 3 a[3]$
$F(1) = 3 a[0] + 0 a[1] + 1 a[2] + 2 a[3]$

$F(1) - F(0) = 3 a[0] - a[1] - a[2] - a[3]$

Or equivalently $F(1) - F(0) = 4 a[0] - a[0] - a[1] - a[2] - a[3]$

Solution:

With the equations above, we know rotating once means adding 4 times the first element minus the sum of all elements, this is easy to rotate through and find the maximum!

Code:

#include "stdafx.h"

// https://leetcode.com/contest/4/problems/rotate-function/

#include "LEET_ROTATE_FUNCTION.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_ROTATE_FUNCTION
{
class Solution {
public:
int maxRotateFunction(vector<int>& A) {
vector<int>& nums = A;

int n = (int)nums.size();
int sum = 0;

for (int i = 0; i < n; i++)
{
sum += nums[i];
}

int r = 0;
for (int i = 0; i < n; i++)
{
r += i * nums[i];
}

int max_r = r;

for (int move = 0; move < n - 1; move++)
{
r = r - sum + nums[move] * nums.size();
if (r > max_r)
{
max_r = r;
}
}

return max_r;
}
};
};

using namespace _LEET_ROTATE_FUNCTION;

int LEET_ROTATE_FUNCTION()
{
Solution solution;
vector<int> v;
v.push_back(4);
v.push_back(3);
v.push_back(2);
v.push_back(6);
cout << solution.maxRotateFunction(v) << endl;
return 0;
}