## 13 September 2014

### Quiz 25: Find the highest sum with N rotations

Problem:
Given an array of numbers. SUM is denoted as 1 * 1st element + 2 * 2nd element +.....+ N * Nth element.
The array can be rotated in such a manner that 1st element goes to last and 2nd element becomes 1st element and SUM can be calculated again. So, for all N rotations find the highest SUM

Input Format:

array elements separated by space

Output Format:
Highest SUM

Constraints:
none

Sample Input
5 -2 4 1 -4

Sample Output:
21

Explanations:-
original string: 5 -2 4 1 -4=> SUM= 5+(2*-2)+(3*4)+(4*1)+(5*-4)=5-4+12+4-20=-3
1st rotation: -2 4 1 -4 5=>SUM= -2+(2*4)+(3*1)+(4*-4)+(5*5)=-1+8+3-16+25=-1
2nd rotation: 4 1 -4 5 -2=>SUM= 4+(2*1)+(3*-4)+(4*5)+(5*-2)=4+2-12+20-10=4
3rd rotation: 1 -4 5 -2 4=>SUM= 1+(2*-4)+(3*5)+(4*-2)+(5*4)=1-8+15-8+20=20
4th rotation: -4 5 -2 4 1=>SUM= -4+(2*5)+(3*-2)+(4*4)+(5*1)=-4+10-6+16+5=21
so highest SUM is 21

Solution:

chomp(\$t=<STDIN>);
@arr=split(" ",\$t);
\$len=@arr;
\$high=0;
for(\$i=1;\$i<=\$len;\$i++)
{
\$high=\$high+(\$arr[\$i-1] * \$i);
}
\$o=\$high;
foreach(@arr)
{
\$sum+=\$_;
}
for(\$j=0;\$j<\$len;\$j++)
{
\$o=\$o-\$sum+(\$len*\$arr[0]);
if(\$o>\$high)
{
\$high=\$o;
}
my \$first = shift @arr;
\$arr[\$len-1]=\$first;
}
print "\$high";

Tips:
After each rotation, SUM changes by previous cycle sum-(sum of all elements)+N*1st element