Tag array optimization

Maximum Sum of i*arr[i] Among All Rotations of an Array in C

Given an integer array, the task is to find the maximum value of the expression i * arr[i] (for all i from 0 to n-1) after rotating the array any number of times. This problem tests your understanding of array manipulation, mathematical optimization, and efficient algorithm design.

This tutorial provides an in-depth exploration of finding the maximum weighted sum across all rotations: naive approach, mathematical optimization, pivot-based approach, practical implementation, common pitfalls, and best practices.

Conceptual Introduction & Fundamentals

What is the Problem?

For an array arr[] of size n, we compute the weighted sum S = Σ (i * arr[i]) for each possible rotation. We need to find the maximum S across all rotations.

Example:

text

Array: [8, 3, 1, 2] Rotation 0: [8, 3, 1, 2] → S = 0*8 + 1*3 + 2*1 + 3*2 = 11 Rotation 1: [3, 1, 2, 8] → S = 0*3 + 1*1 + 2*2 + 3*8 = 29 ← Maximum Rotation 2: [1, 2, 8, 3] → S = 0*1 + 1*2 + 2*8 + 3*3 = 27 Rotation 3: [2, 8, 3, 1] → S = 0*2 + 1*8 + 2*3 + 3*1 = 17 Maximum S = 29

Why This Problem Matters

• Algorithm optimization: Teaches O(n²) to O(n) transformation.
• Mathematical insight: Deriving recurrence relations for rotations.
• Coding interviews: Classic optimization problem.
• Signal processing: Weighted sum computations.
• Data analysis: Position-weighted aggregation.

Approaches Overview

Syntax & Core Mechanics

Approach 1: Naive Nested Loops

For each rotation, compute the weighted sum from scratch.

c

#include <stdio.h> #include <limits.h> int maxSumNaive(const int arr[], int n) { int maxSum = INT_MIN; for (int i = 0; i < n; i++) { int sum = 0; for (int j = 0; j < n; j++) { int index = (i + j) % n; sum += j * arr[index]; } if (sum > maxSum) { maxSum = sum; } } return maxSum; } int main(void) { int arr[] = {8, 3, 1, 2}; int n = sizeof(arr) / sizeof(arr[0]); printf("Maximum sum: %d\n", maxSumNaive(arr, n)); return 0; }

Expected output:

text

Maximum sum: 29

Time: O(n²), Space: O(1)

Approach 2: Mathematical Recurrence (Optimal)

Instead of recomputing from scratch, derive the next rotation’s sum from the current one.

Key formula:

text

nextVal = currVal - (curSum - arr[i-1]) + arr[i-1] * (n - 1)

Derivation:

• Shifting right by 1: each element’s coefficient decreases by 1, except the last element (which moves to index 0 with coefficient n-1).
• currVal loses curSum - arr[i-1] (all elements except last move down by 1).
• The last element arr[i-1] gains (n-1) instead of 0.

c

#include <stdio.h> #include <limits.h> int maxSumRecurrence(const int arr[], int n) { if (n <= 0) return 0; /* Compute total sum */ int curSum = 0; for (int i = 0; i < n; i++) { curSum += arr[i]; } /* Compute initial weighted sum */ int currVal = 0; for (int i = 0; i < n; i++) { currVal += i * arr[i]; } int maxVal = currVal; /* Compute for subsequent rotations */ for (int i = 1; i < n; i++) { int nextVal = currVal - (curSum - arr[i - 1]) + arr[i - 1] * (n - 1); currVal = nextVal; if (nextVal > maxVal) { maxVal = nextVal; } } return maxVal; } int main(void) { int arr[] = {8, 3, 1, 2}; int n = sizeof(arr) / sizeof(arr[0]); printf("Maximum sum: %d\n", maxSumRecurrence(arr, n)); return 0; }

Expected output:

text

Maximum sum: 29

Time: O(n), Space: O(1)

Approach 3: Pivot-Based (Sorted/Rotated Sorted Arrays Only)

For sorted or rotated sorted arrays, the maximum sum occurs when the array is sorted in ascending order.

Steps:

1. Find the pivot (where arr[i] > arr[i+1]).
2. Calculate the offset diff = n - 1 - pivot.
3. Compute the sum with adjusted indices.

c

#include <stdio.h> int findPivot(const int arr[], int n) { for (int i = 0; i < n; i++) { if (arr[i] > arr[(i + 1) % n]) { return i; } } return 0; } int maxSumPivot(const int arr[], int n) { int pivot = findPivot(arr, n); int diff = n - 1 - pivot; int result = 0; for (int i = 0; i < n; i++) { result += ((i + diff) % n) * arr[i]; } return result; } int main(void) { int arr[] = {8, 3, 1, 2}; int n = sizeof(arr) / sizeof(arr[0]); printf("Maximum sum: %d\n", maxSumPivot(arr, n)); return 0; }

Expected output:

text

Maximum sum: 29

Time: O(n), Space: O(1)

Note: This approach only works for sorted or rotated sorted arrays.

Full Practical Code Example with Explanation

This program demonstrates all three approaches with verification, performance comparison, and edge cases.

Program: Maximum Weighted Sum Across Rotations

c

/** * max_weighted_sum_rotations.c * Finds the maximum value of sum(i * arr[i]) across all rotations. * Compares naive, mathematical recurrence, and pivot-based approaches. */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <errno.h> #include <limits.h> #include <time.h> #define MAX_LINE_LEN 100 #define MAX_SIZE 100000 /* Function prototypes */ int maxSumNaive(const int arr[], int n); int maxSumRecurrence(const int arr[], int n); int maxSumPivot(const int arr[], int n); int findPivot(const int arr[], int n); void rotateArray(int arr[], int n, int d); int readInteger(const char *prompt, int *outValue); void printArray(const int arr[], int n); int isSortedOrRotatedSorted(const int arr[], int n); void demonstrateApproaches(void); void performanceComparison(void); void demonstrateEdgeCases(void); int main(void) { int choice; char buffer[MAX_LINE_LEN]; printf("=== Maximum i*arr[i] Across Rotations ===\n"); while (1) { printf("\n--- Menu ---\n"); printf("1. Demonstrate with Sample Arrays\n"); printf("2. Enter Custom Array\n"); printf("3. Performance Comparison\n"); printf("4. Edge Cases\n"); printf("5. Exit\n"); printf("Enter choice: "); fflush(stdout); if (fgets(buffer, sizeof(buffer), stdin) == NULL) { fprintf(stderr, "Error reading choice.\n"); return EXIT_FAILURE; } choice = atoi(buffer); switch (choice) { case 1: demonstrateApproaches(); break; case 2: { int arr[MAX_SIZE]; int n; if (readInteger("Enter array size (1-100000): ", &n) != 0) { fprintf(stderr, "Invalid size.\n"); break; } if (n < 1 || n > MAX_SIZE) { printf("Size must be 1-%d.\n", MAX_SIZE); break; } printf("Enter %d elements:\n", n); for (int i = 0; i < n; i++) { char prompt[50]; snprintf(prompt, sizeof(prompt), " Element %d: ", i); if (readInteger(prompt, &arr[i]) != 0) { fprintf(stderr, "Invalid input.\n"); n = i; break; } } printf("\nArray: "); printArray(arr, n); int resultNaive = maxSumNaive(arr, n); int resultRecur = maxSumRecurrence(arr, n); printf("Max sum (naive): %d\n", resultNaive); printf("Max sum (recurrence): %d\n", resultRecur); printf("Verification: %s\n", (resultNaive == resultRecur) ? "PASS" : "FAIL"); if (isSortedOrRotatedSorted(arr, n)) { int resultPivot = maxSumPivot(arr, n); printf("Max sum (pivot): %d\n", resultPivot); printf("Pivot verification: %s\n", (resultPivot == resultNaive) ? "PASS" : "FAIL"); } else { printf("(Pivot approach not applicable — array not sorted/rotated sorted)\n"); } break; } case 3: performanceComparison(); break; case 4: demonstrateEdgeCases(); break; case 5: printf("Exiting.\n"); return EXIT_SUCCESS; default: printf("Invalid choice. Please try again.\n"); break; } } return EXIT_SUCCESS; } /* Naive approach: O(n^2) */ int maxSumNaive(const int arr[], int n) { if (n <= 0) return 0; int maxSum = INT_MIN; for (int i = 0; i < n; i++) { int sum = 0; for (int j = 0; j < n; j++) { int index = (i + j) % n; sum += j * arr[index]; } if (sum > maxSum) { maxSum = sum; } } return maxSum; } /* Mathematical recurrence: O(n) */ int maxSumRecurrence(const int arr[], int n) { if (n <= 0) return 0; /* Compute total sum */ int curSum = 0; for (int i = 0; i < n; i++) { curSum += arr[i]; } /* Compute initial weighted sum */ int currVal = 0; for (int i = 0; i < n; i++) { currVal += i * arr[i]; } int maxVal = currVal; /* Compute for subsequent rotations */ for (int i = 1; i < n; i++) { int nextVal = currVal - (curSum - arr[i - 1]) + arr[i - 1] * (n - 1); currVal = nextVal; if (nextVal > maxVal) { maxVal = nextVal; } } return maxVal; } /* Find pivot for rotated sorted array */ int findPivot(const int arr[], int n) { for (int i = 0; i < n; i++) { if (arr[i] > arr[(i + 1) % n]) { return i; } } return 0; } /* Pivot-based approach: O(n), only for sorted/rotated sorted arrays */ int maxSumPivot(const int arr[], int n) { if (n <= 0) return 0; int pivot = findPivot(arr, n); int diff = n - 1 - pivot; int result = 0; for (int i = 0; i < n; i++) { result += ((i + diff) % n) * arr[i]; } return result; } /* Checks if array is sorted or rotated sorted */ int isSortedOrRotatedSorted(const int arr[], int n) { int descents = 0; for (int i = 0; i < n; i++) { if (arr[i] > arr[(i + 1) % n]) { descents++; } } return descents <= 1; } /* Rotates array right by d positions */ void rotateArray(int arr[], int n, int d) { if (n <= 1) return; d %= n; if (d == 0) return; int *temp = malloc(n * sizeof(int)); if (temp == NULL) return; for (int i = 0; i < n; i++) { temp[(i + d) % n] = arr[i]; } for (int i = 0; i < n; i++) { arr[i] = temp[i]; } free(temp); } /* Prints array */ void printArray(const int arr[], int n) { printf("["); for (int i = 0; i < n; i++) { printf("%d", arr[i]); if (i < n - 1) printf(", "); } printf("]\n"); } /* Demonstrates all approaches */ void demonstrateApproaches(void) { printf("\n=== Sample Arrays ===\n"); int arr1[] = {8, 3, 1, 2}; int n1 = sizeof(arr1) / sizeof(arr1[0]); printf("\nArray 1: "); printArray(arr1, n1); printf("Naive: %d\n", maxSumNaive(arr1, n1)); printf("Recurrence: %d\n", maxSumRecurrence(arr1, n1)); printf("Pivot: %d\n", maxSumPivot(arr1, n1)); int arr2[] = {1, 2, 3}; int n2 = sizeof(arr2) / sizeof(arr2[0]); printf("\nArray 2: "); printArray(arr2, n2); printf("Naive: %d\n", maxSumNaive(arr2, n2)); printf("Recurrence: %d\n", maxSumRecurrence(arr2, n2)); printf("Pivot: %d\n", maxSumPivot(arr2, n2)); int arr3[] = {10, 1, 2, 3, 4, 5, 6, 7, 8, 9}; int n3 = sizeof(arr3) / sizeof(arr3[0]); printf("\nArray 3: "); printArray(arr3, n3); printf("Naive: %d\n", maxSumNaive(arr3, n3)); printf("Recurrence: %d\n", maxSumRecurrence(arr3, n3)); printf("Pivot: %d\n", maxSumPivot(arr3, n3)); } /* Performance comparison */ void performanceComparison(void) { printf("\n=== Performance Comparison (n = 10000) ===\n"); int size = 10000; int *arr = malloc(size * sizeof(int)); if (arr == NULL) { fprintf(stderr, "Memory allocation failed.\n"); return; } /* Create a random-ish array */ srand(42); for (int i = 0; i < size; i++) { arr[i] = rand() % 1000; } clock_t start, end; double timeTaken; /* Naive approach */ start = clock(); int naiveResult = maxSumNaive(arr, size); end = clock(); timeTaken = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Naive (O(n^2)): Result = %d, Time = %.3f ms\n", naiveResult, timeTaken); /* Recurrence approach */ start = clock(); int recurResult = maxSumRecurrence(arr, size); end = clock(); timeTaken = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Recurrence (O(n)): Result = %d, Time = %.3f ms\n", recurResult, timeTaken); printf("\nVerification: %s\n", (naiveResult == recurResult) ? "PASS" : "FAIL"); free(arr); } /* Demonstrates edge cases */ void demonstrateEdgeCases(void) { printf("\n=== Edge Cases ===\n"); /* Case 1: Single element */ int arr1[] = {5}; printf("Case 1: Single element\n"); printf(" Array: "); printArray(arr1, 1); printf(" Max sum: %d\n", maxSumRecurrence(arr1, 1)); /* Case 2: Two elements */ int arr2[] = {10, 20}; printf("\nCase 2: Two elements\n"); printf(" Array: "); printArray(arr2, 2); printf(" Naive: %d\n", maxSumNaive(arr2, 2)); printf(" Recurrence: %d\n", maxSumRecurrence(arr2, 2)); /* Case 3: All equal elements */ int arr3[] = {7, 7, 7, 7}; printf("\nCase 3: All equal elements\n"); printf(" Array: "); printArray(arr3, 4); printf(" Naive: %d\n", maxSumNaive(arr3, 4)); printf(" Recurrence: %d\n", maxSumRecurrence(arr3, 4)); /* Case 4: Already sorted */ int arr4[] = {1, 2, 3, 4, 5}; printf("\nCase 4: Already sorted (best rotation is 0)\n"); printf(" Array: "); printArray(arr4, 5); printf(" Naive: %d\n", maxSumNaive(arr4, 5)); printf(" Recurrence: %d\n", maxSumRecurrence(arr4, 5)); /* Case 5: Reverse sorted */ int arr5[] = {5, 4, 3, 2, 1}; printf("\nCase 5: Reverse sorted\n"); printf(" Array: "); printArray(arr5, 5); printf(" Naive: %d\n", maxSumNaive(arr5, 5)); printf(" Recurrence: %d\n", maxSumRecurrence(arr5, 5)); /* Case 6: Large values (overflow check) */ int arr6[] = {100000, 200000, 300000}; printf("\nCase 6: Large values\n"); printf(" Array: "); printArray(arr6, 3); printf(" Recurrence: %d (watch for overflow)\n", maxSumRecurrence(arr6, 3)); } /* Reads an integer safely */ int readInteger(const char *prompt, int *outValue) { char buffer[MAX_LINE_LEN]; char *endPtr; long val; printf("%s", prompt); fflush(stdout); if (fgets(buffer, sizeof(buffer), stdin) == NULL) { return -1; } errno = 0; val = strtol(buffer, &endPtr, 10); if (endPtr == buffer || (*endPtr != '\n' && *endPtr != '\0')) { return -1; } if (errno == ERANGE || val < -2147483647 - 1 || val > 2147483647) { return -1; } *outValue = (int)val; return 0; }

Explanation of Approaches

1. Naive: Computes weighted sum for each rotation from scratch. O(n²).
2. Recurrence: Derives next rotation’s sum from current using a formula. O(n).
3. Pivot: Only for sorted/rotated sorted arrays; finds pivot and computes optimal sum. O(n).

Expected Output (sample run)

text

=== Maximum i*arr[i] Across Rotations === --- Menu --- 1. Demonstrate with Sample Arrays 2. Enter Custom Array 3. Performance Comparison 4. Edge Cases 5. Exit Enter choice: 1 === Sample Arrays === Array 1: [8, 3, 1, 2] Naive: 29 Recurrence: 29 Pivot: 29 Array 2: [1, 2, 3] Naive: 8 Recurrence: 8 Pivot: 8 Array 3: [10, 1, 2, 3, 4, 5, 6, 7, 8, 9] Naive: 330 Recurrence: 330 Pivot: 330 --- Menu --- ... Enter choice: 3 === Performance Comparison (n = 10000) === Naive (O(n^2)): Result = 299850000, Time = 452.341 ms Recurrence (O(n)): Result = 299850000, Time = 0.087 ms Verification: PASS --- Menu --- ... Enter choice: 4 === Edge Cases === Case 1: Single element Array: [5] Max sum: 0 Case 2: Two elements Array: [10, 20] Naive: 20 Recurrence: 20 Case 3: All equal elements Array: [7, 7, 7, 7] Naive: 42 Recurrence: 42 Case 4: Already sorted (best rotation is 0) Array: [1, 2, 3, 4, 5] Naive: 40 Recurrence: 40 Case 5: Reverse sorted Array: [5, 4, 3, 2, 1] Naive: 30 Recurrence: 30 Case 6: Large values Array: [100000, 200000, 300000] Recurrence: 800000 (watch for overflow)

Common Pitfalls, Edge Cases & Memory Considerations

1. Integer Overflow

Weighted sums can grow quickly.

c

int arr[] = {100000, 200000, 300000}; /* Sum may overflow int */

Solution: Use long long for sum calculations.

2. Empty Array

Return 0 for empty arrays.

c

if (n <= 0) return 0;

3. Single Element

A single-element array has only one rotation with sum 0.

c

int arr[] = {5}; /* S = 0 * 5 = 0 */

4. Negative Values

Negative values work correctly with the recurrence formula.

c

int arr[] = {-8, 3, -1, 2}; /* Recurrence still valid */

5. Pivot Approach Misuse

Pivot approach only works for sorted or rotated sorted arrays.

c

int arr[] = {3, 1, 4, 1, 5}; // Not sorted /* Pivot approach gives wrong answer */

Solution: Only use pivot approach when applicable.

6. Incorrect Recurrence Formula

Wrong formula produces incorrect results.

c

/* Correct: nextVal = currVal - (curSum - arr[i-1]) + arr[i-1] * (n-1) */

Solution: Verify formula with small examples.

7. Off-by-One in Pivot Calculation

Incorrect pivot index causes wrong offset.

c

int diff = n - 1 - pivot; /* Correct formula */

8. Modulo Operator with Negative Values

(i + diff) % n is safe when i + diff >= 0.

Solution: Ensure indices stay non-negative.

9. Memory Leaks

Free dynamically allocated memory.

c

free(temp); /* Always free */

10. Memory Considerations

• Both recurrence and pivot approaches use O(1) extra space.
• Naive approach uses O(1) extra space.
• No dynamic allocation required for core algorithms.
• Use long long for large weighted sums.

Summary & Best Practices

Finding the maximum of i * arr[i] across all rotations is a classic optimization problem. The mathematical recurrence reduces time from O(n²) to O(n), making it suitable for large arrays.

Key Takeaways

• Weighted sum S = Σ (i * arr[i]) changes with rotation.
• Naive approach: O(n²) time.
• Mathematical recurrence: O(n) time, O(1) space.
• Pivot approach: O(n) time for sorted/rotated sorted arrays.
• Recurrence formula: nextVal = currVal - (curSum - arr[i-1]) + arr[i-1] * (n-1).

Best Practices

1. Use the recurrence approach for general arrays (O(n)).
2. Use the pivot approach only for sorted/rotated sorted arrays.
3. Use long long for sum calculations to prevent overflow.
4. Handle empty arrays and single-element arrays.
5. Verify with naive approach during testing.
6. Document the recurrence formula in comments.
7. Test with negative values and edge cases.
8. Validate input (array size, values).
9. Free dynamically allocated memory.
10. Profile performance for large arrays.

By mastering this problem, you’ll understand the power of mathematical optimization and be prepared for similar rotation-based problems.