Maximum Productivity After Employee Rearrangement | Dynamic Programming Assignment Problem

HackFury

Published : 08 June 2026

30 Views

#array

#greedy

#dynamic-programming

#coding-problems

#dsa

You are given an array A of length N, where:

A[i] represents the productivity score of the employee initially sitting at seat i (1-indexed).
Before the workday begins, the manager can perform exactly one global rearrangement of all employees.
Every employee must be assigned to a unique seat.

If an employee originally sitting at position x is moved to position y, that employee contributes:

A[x] × ∣x − y∣

to the team's total productivity score.

Your task is to determine the maximum possible productivity score after rearranging all employees.

Constraints

2 ≤ N ≤ 2000
1 ≤ A[i] ≤ 10^9

Understanding the Problem

Suppose we have:


Position : 1  2  3
Value    : 1  3  2

Employee at position 2 has productivity 3. If we move him from position 2 to position 1:


Contribution = 3 × |2 - 1|
             = 3 × 1
             = 3

Similarly, every employee contributes:

Productivity × Distance Moved

The goal is to maximize:

Σ(Productivity × Distance)

by choosing the best final arrangement.

Brute Force Approach

A straightforward idea would be:

Generate all permutations of employees.
Calculate total productivity for each arrangement.
Return the maximum.

For N = 2000, this is impossible. Number of permutations: 2000! which is astronomically large.

We need a smarter observation.

Key Insight

Consider two employees:

Employee A → productivity = 1000
Employee B → productivity = 5

Moving Employee A by 10 seats gives:

1000 × 10 = 10000

Moving Employee B by 10 seats gives:

5 × 10 = 50

Clearly, high-productivity employees should get the largest movement distances.

This suggests: Process employees in descending order of productivity.

Important Observation

After sorting employees by productivity, suppose we place the most productive employee first.

Where should we place him?

To maximize distance, the best positions are: Leftmost seat or Rightmost seat

For every highly productive employee, we only need to decide: Put him on the left end? or Put him on the right end? This dramatically reduces the search space.

1: Understanding What We Need to Maximize

Each employee starts at a fixed position and has a productivity value associated with them. If an employee originally sitting at position x is moved to position y, their contribution to the final answer becomes:

Productivity×∣x−y∣

The distance moved by the employee is multiplied by their productivity value. This means that moving a highly productive employee even a small distance can contribute more than moving a low-productivity employee a large distance.

Our objective is to rearrange all employees in such a way that the sum of these contributions is maximized.

2: Sorting Employees Is the Key Observation

Consider two employees:


Employee A → Productivity = 1000
Employee B → Productivity = 5

If both employees move by the same distance:

Employee A:

1000 × 10 = 10000

Employee B:

5 × 10 = 50

Clearly, moving Employee A is far more valuable. This tells us something important: The employees with larger productivity values should be given priority when choosing positions that produce large movement distances.

Therefore, instead of processing employees in their original order, we sort them in descending order of productivity and place the most valuable employees first.

Example


Suppose:

Position : 1  2  3  4
Value    : 8  3  5  1

Store:

(8,1)
(3,2)
(5,3)
(1,4)

where:

(Productivity, Original Position)

After sorting:


(8,1)
(5,3)
(3,2)
(1,4)

Now we process employees in this order.

3: Why Only the Leftmost and Rightmost Seats Matter

This is the most important observation of the problem. Suppose initially:


Seats: 1 2 3 4 5

We want to place the highest productivity employee.

Which position should we choose?

Possible choices:


Seat 1
Seat 2
Seat 3
Seat 4
Seat 5

Notice that the largest movement distance is always achieved by one of the extreme positions: Seat 1 or Seat 5

A middle seat can never provide a larger distance than an endpoint.

Therefore, when placing a highly productive employee, the only positions worth considering are: Leftmost available seat or Rightmost available seat

What Happens After One Placement?

Suppose we assign someone to seat 1. Now the seating arrangement looks like:

X 2 3 4 5

The remaining available seats are:

2 3 4 5

Again, for the next employee, the most useful choices are: Seat 2 or Seat 5

which are the two ends of the remaining interval. After another placement:

X 2 3 4 X

Remaining:

2 3 4

Again the next employee only needs to consider: Seat 2 or Seat 4

The same pattern continues throughout the process.

Important Conclusion

At every step: Current employee has only two choices:

Take the leftmost available seat.
Take the rightmost available seat.

This observation dramatically reduces the search space and makes Dynamic Programming possible.

4: Meaning of dp[i][left]

This is the most important part of the entire solution. Many people understand the transitions but get confused about what information the DP state is actually storing. We define:

dp[i][left]

as: The maximum productivity score that can be achieved after placing the first i employees from the sorted list (highest productivity employees first), where exactly left of those employees have been placed on the left side of the arrangement.

Notice that we are not storing the actual arrangement of employees inside the DP state. Doing that would make the state too large and impossible to compute efficiently. Instead, we only store how many employees have already been placed and how many of those placements were made from the left side.

The beauty of this approach is that this small amount of information is enough to reconstruct the current available seating interval. Once we know how many seats have been occupied from the left and right ends, we automatically know which seats are still free.

Example

Suppose:


N = 5
i = 3
left = 2

This means that we have already processed and placed the first 3 employees from the sorted list. Out of those three placements:

2 employees were assigned from the left side.
Since a total of 3 employees have already been placed, the remaining placement must have come from the right side.

rightUsed = i - left
          = 3 - 2
          = 1

So our current situation is:

Left placements = 2
Right placements = 1

which means the seats must look like:


1  2  3  4  5
X  X  _  _  X

Even though we never stored this arrangement explicitly, we can derive it entirely from i and left.

5: Why Can We Calculate Remaining Seats From Only left?

At first glance, it may seem impossible to know which seats are still available without storing the complete seating arrangement. However, because employees are always assigned to one of the two ends of the remaining interval, the arrangement follows a very predictable structure.

Whenever we place an employee, we either consume the leftmost available seat or the rightmost available seat. As a result, occupied seats gradually grow inward from both ends, while the unoccupied seats always remain together in the middle.

Because of this property, knowing:

Total employees placed = i
Employees placed on left = left
automatically tells us: Employees placed on right = i - left

and therefore the exact interval of remaining seats.

This is why the DP state only needs two dimensions instead of storing the complete arrangement.

6: Finding the Next Available Left Seat

Once we know how many seats have already been occupied from the left side, determining the next available left seat becomes straightforward.

If: left = 2
then seats: 1 and 2 are already occupied.
Therefore, the next free seat on the left side must be: leftPos = left + 1; which gives: leftPos = 3

This formula works for every state because left-side placements always occur consecutively from the beginning of the array.

7: Finding the Next Available Right Seat

Similarly, once we know how many seats have been consumed from the right side, we can determine the next free seat on the right.

Suppose:

N = 5
rightUsed = 1
Then seat: 5 has already been occupied.
Therefore the next available right seat becomes: rightPos = N - rightUsed = 5 - 1 = 4

This formula works because right-side placements always occur consecutively from the end of the array.

8: Processing the Current Employee

Suppose the sorted employees are:


(8,1)
(5,3)
(3,2)
(1,4)

and we are currently processing:

(3,2)

This means:

Productivity = 3
Original Position = 2
Assume our DP state is: i = 2 and left = 1
This tells us: rightUsed = 1
and the current seat configuration is:

1 2 3 4
X _ _ X

The only available seats are: 2 and 3

Since every future arrangement must keep consuming seats from the ends of the remaining interval, these are the only two valid positions we need to consider.

9: Choice 1 – Place the Employee on the Left

If we assign the current employee to the leftmost available seat, he will be placed at: Seat 2 His movement distance becomes: |2 - 2| = 0 and therefore his contribution is: 3 × 0 = 0

Since we used one more seat from the left side, the number of left placements increases by one. This is why the next state becomes:

dp[i+1][left+1]

The DP transition adds the employee's contribution to the best score already achieved in the current state.


dp[i+1][left+1] =
max(
    dp[i+1][left+1],
    dp[i][left] +
    value * abs(pos - leftPos)
);

10: Choice 2 – Place the Employee on the Right

Instead of using the left seat, we may assign the employee to the rightmost available seat. That seat is: Seat 3 The movement distance becomes: |2 - 3| = 1 giving a contribution of: 3 × 1 = 3

Since the employee was placed on the right side, the count of left placements remains unchanged. Therefore the next state remains:

dp[i+1][left]

The DP compares this score with any previously computed value for the same state and keeps the maximum.


dp[i+1][left] =
max(
    dp[i+1][left],
    dp[i][left] +
    value * abs(pos - rightPos)
);

11: Why This DP Is Correct

The correctness of the solution comes from two fundamental observations.

First, employees are processed in descending order of productivity, ensuring that the most valuable employees get the first opportunity to occupy positions that generate large movement distances.
Second, after every placement, the remaining free seats always form one continuous interval. Because of this property, the next employee only needs to choose between the two endpoints of that interval. No other seat can produce a better arrangement that is not already represented by one of these choices.

The DP explores every possible sequence of left-end and right-end decisions. Since every valid final arrangement can be represented as a sequence of such decisions, the optimal arrangement is guaranteed to be considered. Therefore, the maximum value stored in the final DP row is the answer.

Complexity Analysis

Sorting: O(N log N)
DP States: O(N²)
Transition Cost: O(1)
Total Time Complexity: O(N²)
Space Complexity: O(N²)

This efficiently solves the problem for N ≤ 2000.

DP Visualization

Consider: N = 4
After placing two employees: Seats: [ X _ _ X ]
Used: left = 1 and right = 1
Remaining: [ _ _ ]
Next employee can only go: leftmost remaining seat or rightmost remaining seat
which preserves the DP structure.

#include <bits/stdc++.h>
using namespace std;

long long maximizeProductivity(int N, vector<long long>& A)
{
    vector<pair<long long, int>> employees;
    for (int i = 0; i < N; i++)
    {
        employees.push_back({A[i], i + 1});
    }
    sort(employees.begin(), employees.end(),
         [](const auto& a, const auto& b)
         {
             return a.first > b.first;
         });
    // Initialize unreachable DP states with a very small value.
    // Avoid using LLONG_MIN since adding to it may cause overflow.
    const long long NEG = -(1LL << 60);
    vector<vector<long long>> dp(
        N + 1,
        vector<long long>(N + 1, NEG));

    dp[0][0] = 0;
    for (int i = 0; i < N; i++)
    {
        auto [value, pos] = employees[i];
        for (int left = 0; left <= i; left++)
        {
            if (dp[i][left] == NEG)
                continue;
            int rightUsed = i - left;
            int leftPos = left + 1;
            int rightPos = N - rightUsed;
            // Place at left end
            dp[i + 1][left + 1] =
                max(dp[i + 1][left + 1],
                    dp[i][left] +
                    value * abs(pos - leftPos));
            // Place at right end
            dp[i + 1][left] =
                max(dp[i + 1][left],
                    dp[i][left] +
                    value * abs(pos - rightPos));
        }
    }

    long long answer = 0;
    for (int left = 0; left <= N; left++)
    {
        answer = max(answer, dp[N][left]);
    }
    return answer;
}

int main()
{
    int N;
    cin >> N;
    vector<long long> A(N);
    for (int i = 0; i < N; i++)
    {
        cin >> A[i];
    }
    cout << maximizeProductivity(N, A) << endl;
    return 0;
}

import java.util.*;

public class Main {

    public static long maximizeProductivity(int N, long[] A) {
        Employee[] employees = new Employee[N];
        for (int i = 0; i < N; i++) {
            employees[i] = new Employee(A[i], i + 1);
        }
        Arrays.sort(employees, (a, b) -> Long.compare(b.value, a.value));
        // Use a large negative value to represent unreachable DP states.
        // Avoid Long.MIN_VALUE directly, since adding to it can overflow.
        long NEG = Long.MIN_VALUE / 4;
        long[][] dp = new long[N + 1][N + 1];
        for (int i = 0; i <= N; i++) {
            Arrays.fill(dp[i], NEG);
        }
        dp[0][0] = 0;
        for (int i = 0; i < N; i++) {
            long value = employees[i].value;
            int pos = employees[i].position;
            for (int left = 0; left <= i; left++) {
                if (dp[i][left] == NEG)
                    continue;
                int rightUsed = i - left;
                int leftPos = left + 1;
                int rightPos = N - rightUsed;
                dp[i + 1][left + 1] = Math.max(
                        dp[i + 1][left + 1],
                        dp[i][left] + value * Math.abs(pos - leftPos));
                dp[i + 1][left] = Math.max(
                        dp[i + 1][left],
                        dp[i][left] + value * Math.abs(pos - rightPos));
            }
        }

        long answer = 0;
        for (int left = 0; left <= N; left++) {
            answer = Math.max(answer, dp[N][left]);
        }
        return answer;
    }

    static class Employee {
        long value;
        int position;
        Employee(long value, int position) {
            this.value = value;
            this.position = position;
        }
    }

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        long[] A = new long[N];
        for (int i = 0; i < N; i++) {
            A[i] = sc.nextLong();
        }
        System.out.println(maximizeProductivity(N, A));
        sc.close();
    }
}

using System;
using System.Collections.Generic;

public class Program
{
    public static long MaximizeProductivity(int N, long[] A)
    {
        List<(long value, int pos)> employees = new();
        for (int i = 0; i < N; i++)
        {
            employees.Add((A[i], i + 1));
        }
        employees.Sort((a, b) => b.value.CompareTo(a.value));
        long NEG = long.MinValue / 4;
        long[,] dp = new long[N + 1, N + 1];
        for (int i = 0; i <= N; i++)
        {
            for (int j = 0; j <= N; j++)
            {
                dp[i, j] = NEG;
            }
        }
        dp[0, 0] = 0;
        for (int i = 0; i < N; i++)
        {
            long value = employees[i].value;
            int pos = employees[i].pos;
            for (int left = 0; left <= i; left++)
            {
                if (dp[i, left] == NEG)
                    continue;

                int rightUsed = i - left;
                int leftPos = left + 1;
                int rightPos = N - rightUsed;
                dp[i + 1, left + 1] = Math.Max(
                    dp[i + 1, left + 1],
                    dp[i, left] + value * Math.Abs(pos - leftPos));

                dp[i + 1, left] = Math.Max(
                    dp[i + 1, left],
                    dp[i, left] + value * Math.Abs(pos - rightPos));
            }
        }

        long answer = 0;
        for (int left = 0; left <= N; left++)
        {
            answer = Math.Max(answer, dp[N, left]);
        }
        return answer;
    }

    public static void Main()
    {
        int N = int.Parse(Console.ReadLine());
        long[] A = Array.ConvertAll(
            Console.ReadLine().Split(),
            long.Parse);
        Console.WriteLine(
            MaximizeProductivity(N, A));
    }
}

def maximizeProductivity(N, A):
    employees = []
    for i, value in enumerate(A):
        employees.append((value, i + 1))
    employees.sort(reverse=True)
    NEG = -10**30
    dp = [[NEG] * (N + 1) for _ in range(N + 1)]
    dp[0][0] = 0
    for i in range(N):
        value, pos = employees[i]
        for left in range(i + 1):
            if dp[i][left] == NEG:
                continue
            right_used = i - left
            left_pos = left + 1
            right_pos = N - right_used
            dp[i + 1][left + 1] = max(
                dp[i + 1][left + 1],
                dp[i][left] + value * abs(pos - left_pos)
            )

            dp[i + 1][left] = max(
                dp[i + 1][left],
                dp[i][left] + value * abs(pos - right_pos)
            )
    return max(dp[N])

def main():
    N = int(input())
    A = list(map(int, input().split()))

    print(maximizeProductivity(N, A))

if __name__ == "__main__":
    main()

Takeaways

This problem is a classic example of:

Dynamic Programming on permutations
Assignment optimization
Greedy ordering + DP
Interval DP / Left-Right placement DP

The crucial observation is that after sorting employees by productivity, every employee only needs to choose between the leftmost and rightmost available seat. This transforms an impossible N! permutation problem into an efficient O(N²) dynamic programming solution.