## Intuition The problem requires us to find an arrangement of integers such that the sum of differences between adjacent elements is maximized. The key insight is that the maximum difference between adjacent elements can be achieved by alternating between the largest and smallest remaining elements. This is because the largest difference between two numbers is achieved when they are far apart in value. ## Approach 1. **Sort the Array**: Start by sorting the array. This helps us easily access the smallest and largest elements. 2. **Two Pointers Technique**: Use two pointers, one starting at the beginning (smallest element) and the other at the end (largest element) of the sorted array. 3. **Construct the Arrangement**: Alternate between picking elements from the end and the beginning of the sorted array: - Start by picking the largest element (end pointer) and then the smallest element (start pointer). - Continue this process until all elements are used. 4. **Lexicographical Order**: The sorted array ensures that when we alternate between the largest and smallest elements, the sequence remains lexicographically smallest among all possible sequences with the maximum sum of differences. 5. **Output the Result**: Print the constructed sequence. ## Complexity - **Time Complexity**: O(n log n) due to the sorting step. - **Space Complexity**: O(n) for storing the result sequence. ## Solution (C++) ```cpp #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector a(n); for (int i = 0; i < n; ++i) { cin >> a[i]; } // Sort the array sort(a.begin(), a.end()); vector result; int left = 0, right = n - 1; // Alternate between the largest and smallest remaining elements while (left <= right) { if (right >= left) { result.push_back(a[right--]); } if (left <= right) { result.push_back(a[left++]); } } // Output the result for (int i = 0; i < n; ++i) { cout << result[i] << " "; } cout << endl; return 0; } ``` This solution effectively constructs the sequence by alternating between the largest and smallest elements, ensuring both the maximum possible sum of differences and the lexicographically smallest sequence.

Difference Row

Problem Details