0761EasyArrayGreedySorting

Largest Ledger Total After Forced Sign Flips

Tracked in this browser only

Trains the technique from

LeetCode 1005Maximize Sum Of Array After K Negations

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A ledger holds one signed adjustment per line in entries; an entry may be negative, zero or positive. An auditor is required to perform exactly flips sign reversals. One reversal picks any single line and replaces its value by its negation.

All flips reversals must be performed. Stopping early is not allowed, and the same line may be picked again on a later reversal, so a line can be reversed any number of times.

Return the largest total the ledger can show once all flips reversals have been performed.

Examples

Example 1

Input: entries = [4, -1, 3, -6], flips = 3
Output: 12

Reversing the -6 line three times leaves it at 6, and the ledger reads 4, -1, 3, 6, which totals 12. All three reversals have been used.

Example 2

Input: entries = [2, 5, 9], flips = 3
Output: 12

Reversing the 2 line three times leaves the ledger reading -2, 5, 9, which totals 12. The three reversals are all accounted for.

Example 3

Input: entries = [-8, -7, -6, -5], flips = 2
Output: 4

Reversing the -8 line and the -7 line once each leaves the ledger reading 8, 7, -6, -5, which totals 4.

Constraints

1 <= entries.length <= 10^4
-100 <= entries[i] <= 100
1 <= flips <= 10^4

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def best_ledger_total(entries: list[int], flips: int) -> int:

Java

public int bestLedgerTotal(int[] entries, int flips)

The intended approach

Time O(n log n) for n lines, dominated by the sort.Space O(n) for the sorted working copy.

Sort the lines ascending and reverse the most negative line first, then the next, stopping when either the reversals run out or the remaining lines are already non-negative. Every reversal spent that way turns a subtraction into an addition. If reversals are left over, two of them applied to the same line cancel, so only an odd remainder costs anything, and the cheapest place to absorb it is the smallest value now on the ledger, which loses twice its own size.

Pythonentry point: best_ledger_total

def best_ledger_total(entries, flips):
    # Time O(n log n) for the sort, space O(n) for the working copy.
    vals = sorted(entries)
    left = flips
    i = 0
    n = len(vals)
    while i < n and left > 0 and vals[i] < 0:
        vals[i] = -vals[i]
        left -= 1
        i += 1
    total = sum(vals)
    if left % 2 == 1:
        total -= 2 * min(vals)
    return total

The obvious version

A line ends up negated exactly when it is reversed an odd number of times, so try every subset of lines to negate, keep only those whose size is at most `flips` and matches its parity, and take the best total. Exponential in the number of lines.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_best_ledger_total(entries, flips):
    n = len(entries)
    best = None
    for mask in range(1 << n):
        chosen = bin(mask).count("1")
        if chosen > flips or (flips - chosen) % 2 != 0:
            continue
        total = 0
        for i in range(n):
            total += -entries[i] if (mask >> i) & 1 else entries[i]
        if best is None or total > best:
            best = total
    return best

How this problem was checked

Reference solution executed against 13 test cases — 13 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in