logoChat01.ai

Given an array A, you can rearrange the elements o...

생성일: 2025년 9월 3일

답변에 사용된 모델 GPT-5 Thinking by Chat01

질문

Given an array A, you can rearrange the elements of A and let array of prefix sum of A be ‘pref’, maximize summation(((-1)^i)* pref) and return this max value.

code in java

Python

python
import itertools, random

def max_value(arr):
    n=len(arr)
    best=-10**18
    for perm in itertools.permutations(arr):
        pref=0
        total=0
        for i,x in enumerate(perm):
            pref+=x
            total+= ((-1)**i)*pref
        best=max(best,total)
    return best

def formula(arr):
    arr=sorted(arr)
    n=len(arr)
    if n%2==1:
        m=(n+1)//2
        return sum(arr[-m:])
    else:
        m=n//2
        return -sum(arr[:m])

for n in range(1,6):
    for _ in range(50):
        arr=[random.randint(-5,5) for __ in range(n)]
        if max_value(arr)!=formula(arr):
            print("Mismatch", n, arr, max_value(arr), formula(arr))
            raise SystemExit
print("All ok")

사고

Providing Java code with handling for large sums

With 0-based indexing, the formula works well. Java’s long type should suffice to avoid overflow, but for very large numbers, BigInteger might be necessary. Sorting is O(n log n), and computations like prefix sums could exceed int range, so we'll use long. We’ll clarify the indexing assumption and choose whether to also address 1-based indexing.

Delivering code with explanation

We’ll provide the code assuming 0-based indexing, as per the formula. For users with 1-based indexing, they can adapt the code by swapping the logic for even and odd n. The code will return the maximum value for S, using long for sum calculations to avoid overflow.

Coding the solution

We’ll use long[] to handle potential overflow when summing the elements. The method maxAlternatingPrefSum will work with an integer array, but we cast to long for the sum. We’ll sort the array, then sum accordingly: if n is odd, we add the largest elements; if even, subtract the smallest ones. For complexity, it will be O(n log n). Let’s produce the Java code with a sample test.

Thought for 1m 9s

답변

Here’s a clean, optimal solution in Java.

Idea (0-based i):
If we define pref[i] = A[0] + … + A[i] and maximize
S = Σ_{i=0..n-1} (-1)^i * pref[i], then only elements placed at indices with the same parity as n-1 affect S.

  • If n is odd, the contributing indices are even with + sign ⇒ put the largest ⌈n/2⌉ elements there ⇒ S = sum(largest ⌈n/2⌉).
  • If n is even, the contributing indices are odd with − sign ⇒ put the smallest n/2 elements there ⇒ S = − sum(smallest n/2).

So we only need to sort once.

java
import java.util.Arrays;

public class MaxAltPrefSum {
    /**
     * Returns max over all permutations of A of:
     *    S = sum_{i=0..n-1} (-1)^i * pref[i],
     * where pref[i] = sum_{k=0..i} A[k].
     *
     * Time:  O(n log n) due to sort
     * Space: O(1) extra (sorting in place)
     */
    public static long maxAlternatingPrefSum(int[] A) {
        int n = A.length;
        Arrays.sort(A); // ascending

        long ans = 0L;
        if ((n & 1) == 1) {
            // n is odd: take sum of largest ceil(n/2) elements
            int m = (n + 1) / 2;
            for (int i = n - 1; i >= n - m; --i) {
                ans += A[i];
            }
        } else {
            // n is even: negative of sum of smallest n/2 elements
            int m = n / 2;
            for (int i = 0; i < m; ++i) {
                ans -= A[i];
            }
        }
        return ans;
    }

    // quick demo
    public static void main(String[] args) {
        System.out.println(maxAlternatingPrefSum(new int[]{3, 1, 2}));      // 5  (place 3,1,2 → pref: 3,4,6 →  +3 -4 +6 = 5)
        System.out.println(maxAlternatingPrefSum(new int[]{-5, -2, 4, 7})); // 7  (n even → -(sum of two smallest: -5 + -2) = 7)
        System.out.println(maxAlternatingPrefSum(new int[]{5}));            // 5
    }
}

📝 If your definition uses 1-based i (i.e., i = 1..n and (-1)^1 = -1 for the first prefix), just swap the branches:

  • n even → sum of largest n/2 elements;
  • n odd → negative sum of smallest ⌈n/2⌉ elements.

이 Q&A 공유하기