algoadvance

Leetcode 1005. Maximize Sum Of Array After K Negations

Problem Statement

Given an array A of integers, we must perform K operations. In each operation, we can choose an element of the array and change its sign (i.e., we can negate its value). Our goal is to maximize the sum of the array after exactly K operations.

Clarifying Questions

  1. What are the constraints on the values in the array and K?
    • Typical constraints might be: 1 <= A.length <= 10^4, -10^100 <= A[i] <= 10^100, 1 <= K <= 10^4.
  2. Can the array contain duplicate values?
    • Yes, the array can contain duplicate values.
  3. What should be the output?
    • The output should be a single integer that represents the maximum sum of the array after exactly K negations.

Strategy

  1. Sort the Array: First, sort the array. This helps in making decisions on which elements to negate.
  2. Negate the Smallest Elements: Negate the smallest elements first to maximize the sum. Start from the beginning of the sorted array and continue this for K operations or until you run out of negative numbers.
  3. Handle Remaining K: If there are remaining operations and they are odd, negate the smallest absolute value element (this might be the last element negated or a zero if one has been reached).
  4. Sum Up Array: Calculate the sum of the array after the operations.

Code

import java.util.Arrays;

public class MaximizeSumAfterKNegations {
    public int largestSumAfterKNegations(int[] nums, int k) {
        // Step 1: Sort the array
        Arrays.sort(nums);
        
        // Step 2: Negate the smallest (most negative) elements
        for (int i = 0; i < nums.length && k > 0; i++) {
            if (nums[i] < 0) {
                nums[i] = -nums[i];
                k--;
            }
        }
        
        // Step 3: Sort the array again to find the smallest absolute value
        Arrays.sort(nums);

        // Step 4: If k is odd, negate the smallest absolute value element
        if (k % 2 != 0) {
            nums[0] = -nums[0];
        }

        // Step 5: Sum up the array
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        
        return sum;
    }

    public static void main(String[] args) {
        MaximizeSumAfterKNegations solution = new MaximizeSumAfterKNegations();
        int[] nums = {3, -1, 0, 2};
        int k = 3;
        System.out.println(solution.largestSumAfterKNegations(nums, k));  // Output: 6
    }
}

Time Complexity

Overall, the time complexity is dominated by the sorting steps, making it O(n log n).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI