Sort, if all positive, then based on k is even or odd, alternate the value of min. If there are negative values, negate them first, if k is still positive, alternate the min.

Greedy

Sort based on absolute value - So if there are negative nums, we can get bigger sum by negating negative nums with big abs values.

If k is still positive and odd, negate the min.

Given an integer array nums and an integer k, modify the array in the following way:

choose an index i and replace nums[i] with -nums[i]. You should apply this process exactly k times. You may choose the same index i multiple times.

Return the largest possible sum of the array after modifying it in this way.

Example

1 2 3

Input: nums = [2,-3,-1,5,-4], k = 2 Output: 13 Explanation: Choose indices (1, 4) and nums becomes [2,3,-1,5,4].