Show problems as
Classic problem #1005EasyArrayGreedySorting

Maximize Sum Of Array After K Negations

Real-world version: Largest Ledger Total After Forced Sign Flips
Tracked in this browser only
Read Maximize Sum Of Array After K Negations on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def best_ledger_total(entries: list[int], flips: int) -> int:
Java
public int bestLedgerTotal(int[] entries, int flips)

More on the same topics