CareerCup

package com.algorithm.yahoo;

import java.util.Arrays;

public class Pmean {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] arr1 = { 20, 30, 10 };
		System.out.println("Pmean1 :- " + Pmeans(arr1));
	}

	private static int Pmeans(int[] arr1) {
		// TODO Auto-generated method stub
		Arrays.sort(arr1);
		int j = 1;
		int result = 0;
		for (int i : arr1) {
			result += i * j;
			j++;
		}
		return result;
	}

}

Suppose that an array(Arr) has 'N' elements {a, b, c, d, e, ....}.
Array indexing starts at 1.

Define S=a+b+c+d+e+.....

We will have
PMEAN1 = a + 2b + 3c + 4d + 5e + .....
PMEAN2 = b + 2c + 3d + 4e + .....+Na
..
..
PMEAN(k)=PMEAN(k-1) - S + N*Arr[k-1]

Solution in C++:

#include <vector>

int pmean(const std::vector<int> &V)
{
	int n = V.size();
	int i;
	int sum = 0;
	int pmean = 0;
	int best = 0;
	
	for (i = 0; i < n; ++i) {
		sum += V[i];
	}

	for (i = 0; i < n; ++i) {
		pmean += V[i] * (i+1);
	}
	best = pmean;

	for (i = 0; i < (n-1); ++i) {
		pmean -= sum;
		pmean += V[i] * n;
		if (pmean > best) {
			best = pmean;
		}
	}

	return best;
}

PMean[i+1] = PMean[i] - TS + n*A[i]

TS = Total sum of array
A[i] = ith element in the array A

sort the array first then apply the calculation.

def pmean(array):
sum = 0
for n in range(len(array)):
sum += array[n] * n+1
return sum

def max_pmean(array):
if len(array) == []:
return 0
elif len(array) == 1:
return array[0]
else:
max_p = pmean(array)
for i in range(len(array)):
missing_i_array = array[0:i] + array[i+1:]
p_mean_missing_i_array = max_pmean(missing_i_array)
temp_pmean = p_mean_missing_i_array + len(array)*array[i]
if temp_pmean > max_p:
max_p = temp_pmean
last_number = array[i]
return max_p

print max_pmean([10,20,30])

Use Pmean1 and then use the fact that as you rotate left
each value moves to one smaller location.

This means you are multiplying that
number with one less than prev location.
For eg
for PMEAN1 : 10 was multiplied by 3
for PMEAN2 : 10 is multiplied by 2
for PMEAN3 : 10 is multiplied by 1

This means for each successive rotation: you subtract PMEAN by 10.

you do the same for all entries except for the first. As the first moves to the last location
so you multiply that by (index).

Illustratively:

PMEAN1 = 0 + 1*20 + 2*30 + 3*10 = 110
PMEAN2 = 110 + (3-1)*20 - 30 - 10 = 110
and so on...

C++ implementation

#include <vector>

size_t MaxSumOfElementsTimeIndicesViaRotation(const std::vector<size_t> input)
{
    size_t fPrev = 0;
    size_t sum = 0;
    size_t index = 1;
    for (auto x : input) {
        fPrev += x*index;
        sum += x;
        ++index;
    }

    size_t maxVal = fPrev;
    const size_t SizeOfInput = input.size();
    size_t fCur;
    for (index = 1; index < SizeOfInput; ++index) {
        fCur = fPrev + input[index - 1] * SizeOfInput - sum;
        if (fCur > maxVal) {
            maxVal = fCur;
        }
        fPrev = fCur;
    }

    return maxVal;
}

See the sub-problem deduction:cpluspluslearning-petert.blogspot.co.uk/2015/02/data-structure-and-algorithm-max-sum-of.html

def pMean():
    pass
    arrayItems = [10,30,20]
    sum = 0
    arrayItems.insert(0, 0)
    arrayItems.sort()
    for i in range(len(arrayItems)):
        sum += i* arrayItems[i] 
    print sum
    
if __name__ == '__main__':
    pass

pMean()

def pMean():
pass
arrayItems = [10,30,20]
sum = 0
arrayItems.insert(0, 0)
arrayItems.sort()
for i in range(len(arrayItems)):
sum += i* arrayItems[i]
print sum

if __name__ == '__main__':
pass

pMean()

Pmean max is when the largest value has the largest weight and the next largest has the next largest weight.

By weight I mean index value.

Apply Quicksort to sort the numbers
-Calculate the PMEAN formula

def pmeans_alt(array_test):

    loops  = len(array_test)
    pnt = 0;
    means = []
    while pnt < loops:
        total = 0
        for i,x in enumerate(array_test):
        
            total += (i+1)*x

        means.append(total)
        print array_test
        ##now pop and insert at the beginning
        final_element = array_test[loops-1]
        array_test.pop()
        array_test.insert(0,final_element);
        pnt += 1

    print "total means added",len(means)
    max_mean = 0
    for x in means:
        print x
        if x > max_mean:
            max_mean = x

    print "max mean: ",max_mean

def pmeans_alt(array_test):

    loops  = len(array_test)
    pnt = 0;
    means = []
    while pnt < loops:
        total = 0
        for i,x in enumerate(array_test):
        
            total += (i+1)*x

        means.append(total)
        print array_test
        ##now pop and insert at the beginning
        final_element = array_test[loops-1]
        array_test.pop()
        array_test.insert(0,final_element);
        pnt += 1

    print "total means added",len(means)
    max_mean = 0
    for x in means:
        print x
        if x > max_mean:
            max_mean = x

    print "max mean: ",max_mean

public static int getPMean(int nums[]){
		int maxPMeanValue = Integer.MIN_VALUE;
		for(int i =0; i<nums.length;i++){
			int pmean = calcuateMean(nums, i);
			if(pmean > maxPMeanValue){
				maxPMeanValue = pmean;
			}
		}
		return maxPMeanValue;
	}
	
	private static int calcuateMean(int nums[], int startIndex){
		int sum = 0;
		int n = nums.length;
		for(int i =0; i<nums.length;i++){
			sum = sum + (nums[startIndex] *(i+1));
			startIndex = (startIndex+1)%n;
		}
		return sum;
	}

}