LeetCode 1005: Maximize Sum Of Array After K Negations Solution

Master LeetCode problem 1005 (Maximize Sum Of Array After K Negations), a easy challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1005. Maximize Sum Of Array After K Negations

Easy

Array Greedy Sorting

Problem Explanation

Explanation

To maximize the sum of the array after k negations, we want to make the smallest negative numbers positive. To do this, we can repeatedly find the smallest negative number and negate it until we have performed k negations.

Sort the array in non-decreasing order.
Iterate over the array and negate the smallest negative number k times.
If there are still negations left, and k is odd, negate the smallest positive number.

Time complexity: O(n log n) where n is the size of the array (due to sorting).
Space complexity: O(1)

Solution Code

import java.util.Arrays;

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);
        
        int i = 0;
        while (k > 0 && i < nums.length && nums[i] < 0) {
            nums[i] = -nums[i];
            k--;
            i++;
        }
        
        if (k > 0 && k % 2 != 0) {
            Arrays.sort(nums);
            nums[0] = -nums[0];
        }
        
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        
        return sum;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1005 (Maximize Sum Of Array After K Negations)?

This page provides optimized solutions for LeetCode problem 1005 (Maximize Sum Of Array After K Negations) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1005 (Maximize Sum Of Array After K Negations)?

The time complexity for LeetCode 1005 (Maximize Sum Of Array After K Negations) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1005 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1005 in Java, C++, or Python.

Back to LeetCode Solutions