1.拿到这题感觉十分复杂因为如果将所有情况列出来会发现小分支很多。符合题意的根本原则便是尽可能将负数变为正数如果k过大则尽可能将最小的正数变为负数来减少损失。将每一种元素的个数统计到哈希数组中同时根据统计数组中负数的数量negativeNum可以分为如下几种情况1negativeNum k即数组中的负数可以全部转换为正数。因为同一个数组元素可以多次进行转换所以还需要分为两种情况①(k - negativeNum) % 2 0即剩余转换次数为偶数此时将任一正数连续转换剩余次数即可最大值没有发生变化。②(k - negativeNum) % 2 1即剩余转换次数为偶数由于当前数组全部都已经变为正数此时必须将一个最小的正数变为负数。2negativeNum k即数组中的负数无法全部转换为正数。此时就要根据哈希数组来将最小的那部分负数尽可能地转换为正数根据当前已经转换的负数个数cnt此时又分为两种情况①cnt hash[i] k即下一次转换后不会超出转换次数限制直接转换即可。②cnt hash[i] k即下一次转换后会超出转换次数限制需要特殊处理将当前元素中的剩余次数个负数转换剩余负数不转换。2.基于以上思想写出的完整代码如下1. int largestSumAfterKNegations(int* nums, int numsSize, int k) { 2. // 存储最终数组总和 3. int res 0; 4. 5. // negativeNum数组中负数的总个数 6. int negativeNum 0; 7. // hash数组映射数值[-100,100]到下标[0,200]统计每个数字出现次数 8. int hash[201] {0}; 9. // positiveMin数组中最小的非负数 10. int positiveMin INT_MAX; 11. // negativeMax数组中最接近0的负数最大负数 12. int negativeMax INT_MIN; 13. for (int i 0; i numsSize; i){ 14. // 数值偏移100存入哈希计数数组 15. hash[nums[i] 100]; 16. if (nums[i] 0){ 17. negativeNum; 18. // 更新最大负数离0最近的负数 19. negativeMax fmax(negativeMax, nums[i]); 20. } else { 21. // 更新最小非负数 22. positiveMin fmin(positiveMin, nums[i]); 23. } 24. } 25. 26. // 情况1负数总数 ≤ 翻转次数k所有负数全部翻成正数 27. if (negativeNum k){ 28. // 全部数字取绝对值累加求和 29. for (int i 0; i 201; i){ 30. res hash[i] * abs(i - 100); 31. } 32. // 剩余翻转次数为奇数必须再翻转一个数总和会减少两倍最小绝对值 33. if ((k - negativeNum) % 2 1){ 34. int minAbs; 35. // 同时存在正数和负数取两者绝对值更小的 36. if (positiveMin ! INT_MAX negativeMax ! INT_MIN){ 37. minAbs fmin(positiveMin, -negativeMax); 38. } else if (positiveMin ! INT_MAX){ 39. // 只有正数 40. minAbs positiveMin; 41. } else { 42. // 只有负数 43. minAbs -negativeMax; 44. } 45. // 减去两倍最小绝对值翻转一次该数总和变化 -2*minAbs 46. res - 2 * minAbs; 47. } 48. } else { 49. // 情况2负数总数 k只翻转k个绝对值最大的负数即数值最小的负数 50. int cnt 0; 51. for (int i 0; i 201; i){ 52. // 还没翻转够k个负数当前区间是负数区间 53. if (cnt k){ 54. // 当前数字全部翻转也达不到k次全部取绝对值累加 55. if (cnt hash[i] k){ 56. res hash[i] * abs(i - 100); 57. cnt hash[i]; 58. } else { 59. // 只能翻转一部分当前数字翻转的取绝对值剩余保持原值 60. res (k - cnt) * abs(i - 100); 61. res (cnt hash[i] - k) * (i - 100); 62. cnt k; 63. } 64. continue; 65. } 66. // 剩余数字无需翻转直接原值累加 67. res hash[i] * (i - 100); 68. } 69. } 70. 71. return res; 72. }该算法时间复杂度为O(n C)C为哈希数组长度在该算法中为201空间复杂度为O(1)。3.在写代码的时候遇到了如下细节问题1negativeNum k且(k - negativeNum) % 2 1时如果数组中同时拥有正数和负数那么此时就要比较positiveMin和negativeMax的绝对值哪个更小更小的那个才是需要转换为负数的那个。2negativeNum k且cnt hash[i] k时在执行完部分负数转换的操作后此时转换操作已经全部完成不要忘记将cnt的值置位k。4.其实更简单的方式应该是先将数组排序然后将尽可能多的负数变为正数如果需要变换的次数多于负数个数则将最小正数转换。该方法简单易懂一开始我也想到的是这个方法但该方法的时间复杂度为O(nlogn)还是想尽可能降低时间复杂度、写出O(n)的算法。