rotation which gives max sum

Tushar Roy · Tushar Roy · commit 2bdd17c897f8 · 2015-12-30T10:51:43.000-06:00
diff --git a/python/array/rotationwithmaxsum.py b/python/array/rotationwithmaxsum.py
@@ -0,0 +1,20 @@
+# http://www.geeksforgeeks.org/find-maximum-value-of-sum-iarri-with-only-rotations-on-given-array-allowed/
+
+def max_sum(input):
+    arr_sum = 0
+    rotation_sum = 0
+    for i in range(len(input)):
+        arr_sum += input[i]
+        rotation_sum += i*input[i]
+
+    max_rotation_sum = rotation_sum
+
+    for i in range(1, len(input)):
+         rotation_sum += len(input)*input[i-1] - arr_sum
+         max_rotation_sum = max(max_rotation_sum, rotation_sum)
+
+    return max_rotation_sum
+
+if __name__ == '__main__':
+    input = [10, 1, 2, 3, 4, 5, 6, 7, 8, 9]
+    print(max_sum(input))
diff --git a/src/com/interview/array/RotationWithMaxSum.java b/src/com/interview/array/RotationWithMaxSum.java
@@ -0,0 +1,34 @@
+package com.interview.array;
+
+/**
+ * Date 12/30/2015
+ * @author Tushar Roy
+ *
+ * Given an input array find which rotation will give max sum of i * arr[i]
+ *
+ * http://www.geeksforgeeks.org/find-maximum-value-of-sum-iarri-with-only-rotations-on-given-array-allowed/
+ */
+public class RotationWithMaxSum {
+    int maxSum(int input[]) {
+        int arrSum = 0;
+        int rotationSum = 0;
+        for (int i =0; i < input.length; i++) {
+            arrSum += input[i];
+            rotationSum += i*input[i];
+        }
+
+        int maxRotationSum = rotationSum;
+
+        for (int i = 1; i < input.length; i++) {
+            rotationSum += input.length*input[i - 1] - arrSum;
+            maxRotationSum = Math.max(maxRotationSum, rotationSum);
+        }
+        return maxRotationSum;
+    }
+
+    public static void main(String args[]) {
+        int input[] = {10, 1, 2, 3, 4, 5, 6, 7, 8, 9};
+        RotationWithMaxSum rms = new RotationWithMaxSum();
+        System.out.print(rms.maxSum(input));
+    }
+}
