【算法与数据结构】1005、LeetCode K 次取反后最大化的数组和

所有的LeetCode题解索引，可以看这篇文章——【算法和数据结构】LeetCode题解。

一、题目

二、解法

  思路分析：本题允许某个下标的数字多次翻转，因此思路比较简单。首先，我们要求最大和，正数一般不去反转，而是将负数全部翻转过来，如果翻转次数还有剩下那么就将绝对值最小的那个数翻转。程序当中利用了sort函数的重载，根据比较函数的不同对元素进行排序，这里是绝对值降序排列，sort函数的头文件是algorithm。
  程序如下：

class Solution {
static bool cmp(int a, int b) {return abs(a) > abs(b);
}
public:int largestSumAfterKNegations(vector<int>& nums, int k) {sort(nums.begin(), nums.end(), cmp);for (int i = 0; i < nums.size(); i++) {if (nums[i] < 0 && k>0) {nums[i] *= -1; k--;}}if (k % 2 == 1) nums[nums.size() - 1] *= -1;int sum = 0;for (int a : nums) sum += a;return sum;}
};

复杂度分析：

• 时间复杂度： $O(nlogn)$。
• 空间复杂度：$O(1)$。

三、完整代码

# include <iostream>
# include <vector>
# include <algorithm>
using namespace std;class Solution {
static bool cmp(int a, int b) {return abs(a) > abs(b);
}
public:int largestSumAfterKNegations(vector<int>& nums, int k) {sort(nums.begin(), nums.end(), cmp);for (int i = 0; i < nums.size(); i++) {if (nums[i] < 0 && k>0) {nums[i] *= -1; k--;}}if (k % 2 == 1) nums[nums.size() - 1] *= -1;int sum = 0;for (int a : nums) sum += a;return sum;}
};int main() {vector<int> nums = { 2,-3,-1,5,-4 };int k = 2; Solution s1;int result = s1.largestSumAfterKNegations(nums, k);cout << result << endl;system("pause");return 0;
}

end