214.贪心算法：K次取反后最大化的数组和（力扣）

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) 
    {
        int sum = 0;
        
        // 进行k次取反操作
        while (k > 0)
        {
            // 对数组进行排序
            sort(nums.begin(), nums.end());
            // 将最小的元素取反
            nums[0] = -nums[0];
            // 减少k的值
            k--;
        }
        
        // 计算数组的总和
        for (int num : nums)
        {
            sum += num;
        }
        
        return sum;
    }
};

核心思想

• 每次都取反数组中绝对值最小的元素，以确保每次取反操作都对数组总和的影响最小化。
• 通过排序，找到当前数组中的最小元素，并对其进行取反操作。
• 重复上述步骤，直到完成 k 次取反操作。

考虑 nums = [3, -1, 0, 2] 和 k = 3：

1. 第一次操作：

   • 排序后：[-1, 0, 2, 3]
   • 取反最小元素：[1, 0, 2, 3]
   • k = 2

2. 第二次操作：

   • 排序后：[0, 1, 2, 3]
   • 取反最小元素：[0, -1, 2, 3]
   • k = 1

3. 第三次操作：

   • 排序后：[-1, 0, 2, 3]
   • 取反最小元素：[1, 0, 2, 3]
   • k = 0

最后计算总和：1 + 0 + 2 + 3 = 6，返回 6。

原文地址：https://blog.csdn.net/weixin_63779802/article/details/140278581

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！