README
¶
Maximize Sum Of Array After K Negations
贪心算法
负数占用一次转换。然后如果剩下最小的是 0，则可以转换任何多次。如果剩下的次数是偶数，则可以将同一个数字转换两次保持不变；如果剩下的次数是奇数，则将现在最小的数转换为负数则可以。判断现在最小的数可以用当前数字和前一个又负数转换成的数比较大小。
Documentation
¶
Overview ¶
* @lc app=leetcode id=1005 lang=golang * * [1005] Maximize Sum Of Array After K Negations * * https://leetcode.com/problems/maximize-sum-of-array-after-k-negations/description/ * * algorithms * Easy (50.74%) * Likes: 234 * Dislikes: 29 * Total Accepted: 20.8K * Total Submissions: 41K * Testcase Example: '[4,2,3]\n1' * * Given an array A of integers, we must modify the array in the following way: * we choose an i and replace A[i] with -A[i], and we repeat this process K * times in total. (We may choose the same index i multiple times.) * * Return the largest possible sum of the array after modifying it in this * way. * * * * Example 1: * * * Input: A = [4,2,3], K = 1 * Output: 5 * Explanation: Choose indices (1,) and A becomes [4,-2,3]. * * * * Example 2: * * * Input: A = [3,-1,0,2], K = 3 * Output: 6 * Explanation: Choose indices (1, 2, 2) and A becomes [3,1,0,2]. * * * * Example 3: * * * Input: A = [2,-3,-1,5,-4], K = 2 * Output: 13 * Explanation: Choose indices (1, 4) and A becomes [2,3,-1,5,4]. * * * * * * * Note: * * * 1 <= A.length <= 10000 * 1 <= K <= 10000 * -100 <= A[i] <= 100 * *
Source Files