Maximum Scalar Product of Two Vectors: Algorithm and Code

The maximum scalar product of two vectors is always achieved by sorting both arrays in the same order, then summing the products of corresponding elements.

What Is the Scalar Product of Two Vectors?

The scalar product, also called the dot product, maps two equal-length vectors to a single number. For vectors A and B of length n, it is computed as the sum of products of matching positions:

• A · B = A[0] × B[0] + A[1] × B[1] + … + A[n-1] × B[n-1]

The output is always a scalar. It does not produce another vector.

The maximum scalar product problem adds a combinatorial layer: given two arrays, which pairing of elements across all possible permutations produces the largest dot product? Brute force checks every permutation (n! orderings for length n), which becomes infeasible quickly. An array of length 10 already has over 3.6 million permutations. The sorting-based approach solves the same problem in O(n log n).

Why Sorting Gives the Maximum

The rearrangement inequality states that for two real-number sequences, the sum of products is maximized when both are sorted in the same direction. The two-element proof makes the reasoning concrete:

• Let A = [a, b] and B = [c, d], where a is at least b and c is at least d.
• Same-order pairing: a × c + b × d
• Reversed pairing: a × d + b × c
• Difference between the two: (a × c + b × d) - (a × d + b × c) = (a - b) × (c - d)
• Since a is at least b, the factor (a - b) is non-negative.
• Since c is at least d, the factor (c - d) is non-negative.
• The product of two non-negative factors is non-negative, so the same-order pairing always wins or ties.

This extends to n elements by induction. Any two positions that are out of relative order can be swapped to bring them into the same sorted direction, and that swap never decreases the sum. Apply this swap repeatedly until both arrays are fully sorted in the same direction; the result is the maximum dot product.

A direct consequence: the minimum scalar product is obtained by sorting one array ascending and the other descending. This pairs every large element with a small element, minimizing each term’s contribution.

Algorithm Step by Step

The four-step algorithm translates the rearrangement inequality directly:

1. Read both arrays of length n.
2. Sort array 1 in ascending order.
3. Sort array 2 in ascending order.
4. Compute and return the sum of arr1[i] × arr2[i] for i from 0 to n-1.

Sorting both arrays descending instead of ascending also produces the correct maximum. What matters is that both arrays end up in the same order before the element-wise multiplication.

Time complexity: O(n log n) for the sort, O(n) for the scan. Overall O(n log n).

Space complexity: O(1) auxiliary when using an in-place sort (qsort in C, list.sort in Python).

Verified Examples

All examples below are derived from first principles. No answers are taken from the legacy article without re-derivation.

Example 1: Arrays Already in Order

• Input: arr1 = [1, 2, 3], arr2 = [4, 5, 6]
• Both already sorted ascending. No reordering needed.
• Step 1: 1 × 4 = 4
• Step 2: 2 × 5 = 10
• Step 3: 3 × 6 = 18
• Sum: 4 + 10 + 18 = 32
• Maximum scalar product: 32

Example 2: Unsorted Input

• Input: arr1 = [3, 1, 2], arr2 = [6, 4, 5]
• Sort arr1 ascending: [1, 2, 3]. Sort arr2 ascending: [4, 5, 6].
• Computation: 1 × 4 + 2 × 5 + 3 × 6 = 4 + 10 + 18 = 32
• Maximum scalar product: 32
• Note: the result matches Example 1 because the same elements appear in both cases, just in different input order.

Example 3: Arrays with Negative Numbers

• Input: arr1 = [-3, -1, 2], arr2 = [4, -2, 1]
• Sort arr1 ascending: [-3, -1, 2]. Sort arr2 ascending: [-2, 1, 4].
• Computation: (-3) × (-2) + (-1) × 1 + 2 × 4 = 6 + (-1) + 8 = 13
• Maximum scalar product: 13
• Verification using descending sort: [2, -1, -3] paired with [4, 1, -2] gives 2 × 4 + (-1) × 1 + (-3) × (-2) = 8 - 1 + 6 = 13. Same result, confirming correctness.

Code: C and Python

C Program

#include <stdio.h>
#include <stdlib.h>

int compare(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}

int main() {
    int n;
    scanf("%d", &n);
    int arr1[n], arr2[n];
    for (int i = 0; i < n; i++) scanf("%d", &arr1[i]);
    for (int i = 0; i < n; i++) scanf("%d", &arr2[i]);
    qsort(arr1, n, sizeof(int), compare);
    qsort(arr2, n, sizeof(int), compare);
    long long sum = 0;
    for (int i = 0; i < n; i++) sum += (long long)arr1[i] * arr2[i];
    printf("%lld\n", sum);
    return 0;
}

Input format: first line is n, second line is arr1’s n elements space-separated, third line is arr2’s n elements space-separated. For Example 1 (n=3, arr1=1 2 3, arr2=4 5 6), the output is 32.

The compare function uses subtraction rather than direct < comparison to handle negative integers correctly. The cast to long long before multiplication prevents integer overflow when element values are large.

Python Program

n = int(input())
arr1 = list(map(int, input().split()))
arr2 = list(map(int, input().split()))
arr1.sort()
arr2.sort()
print(sum(a * b for a, b in zip(arr1, arr2)))

Both programs sort in ascending order and compute the dot product in a single forward pass. The Python zip function pairs corresponding sorted elements; the generator expression computes each product; sum collapses to a scalar. Output for Example 1: 32.

Minimum vs. Maximum Scalar Product

The minimum scalar product uses the same sorting logic in reverse. Sort one array ascending and the other descending. Every large value in the first array now pairs with a small value in the second array, minimizing each term.

For arr1 = [1, 2, 3] and arr2 = [4, 5, 6]:

• Sort arr1 ascending: [1, 2, 3]. Sort arr2 descending: [6, 5, 4].
• 1 × 6 + 2 × 5 + 3 × 4 = 6 + 10 + 12 = 28
• Minimum scalar product: 28 (compared to maximum of 32)

This is the inverse of the rearrangement inequality: mismatching large with small always minimizes. Knowing both directions from a single theorem saves memorization effort in placement prep.

Where This Appears in Placement Tests

The maximum scalar product belongs to a family of optimal-pairing problems that appear in programming and aptitude rounds. The common thread: an exhaustive search exists but is infeasible, and a greedy observation (sort, then apply a simple rule) collapses the search space to O(n log n).

Related problems you will see in the same category:

• Minimum scalar product (sort one ascending, one descending)
• Arrange numbers to maximize the weighted sum against a fixed weight vector
• Assignment problems: pair n workers with n tasks to minimize total cost (also solved by sorting both sequences and pairing in order of relative efficiency)

The underlying aptitude skill tested is pattern recognition: identifying that the optimal arrangement has structure, not randomness. Students who spot this pattern eliminate the brute-force option immediately and reach the correct algorithm in one step. That saves time across the full test.

For context on how programming and aptitude questions are weighted across leading IT company tests, the campus placement evaluation test guide covers section breakdowns, difficulty distributions, and time limits by company. The placement preparation book guide lists standard references for quantitative aptitude that cover optimal-pairing questions in depth. The time and work aptitude questions article covers another aptitude-quants topic where recognizing a rate-based structure cuts calculation time significantly.

GeeksforGeeks covers additional test cases for the dot product problem including edge cases with duplicates and large-value inputs.

Sorting both arrays to pair large with large is a clean example of constraint-aware optimization: the structure of the problem reveals the structure of the answer. That reasoning pattern shows up in AI systems design. Deciding which model handles which task, and in what sequence, draws on identical logic. TinkerLLM, starting at ₹299, runs hands-on exercises that apply this kind of optimization thinking to real AI workflows, moving from concept to a working implementation in the same session.