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

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

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

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:

@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

## No comments:

## Post a Comment