【贪心】K次取反后最大数组和

解题思路：贪心

遍历数组k次，每次找出最小的元素，将其反转

int findSmallest(int* nums, int numsSize) {
    int min = 0;
    int i;
    for(i = 0; i < numsSize; i++) {
        if(nums[i] < nums[min])
            min = i;
    }
    return min;
}

int largestSumAfterKNegations(int* nums, int numsSize, int k){
    int i;
    for(i = 0; i < k; i++) {
        int index = findSmallest(nums, numsSize);
        nums[index] = -nums[index];
    }

    int ans=0;
    for(i = 0; i < numsSize; i++)
        ans+=nums[i];
    return ans;
}

解题思路：贪心

最优解：先将数组中绝对值最大的负数全部变正。若全变正后k仍不为0，从绝对值最小的数开始转换

1.将数组按照绝对值从大到小排序

2.遍历数组，如果数组元素小于0且k大于0则反转该元素

3.若遍历完数组后k仍大于0，从数组最后一位元素开始遍历

4.最后遍历数组，返回所有元素和

#define abs(x) ((x < 0) ? (~x+1):x)
void sort(int* nums, int numsSize) {
    int i, j;
    for(i = 1; i < numsSize; i++) {
        int temp = nums[i];
        for(j = i-1; j >= 0; j--) {
            if(abs(nums[j]) < abs(temp))
                nums[j+1] = nums[j];
            else
                break;
        }
        nums[j+1] = temp;
    }
}

int largestSumAfterKNegations(int* nums, int numsSize, int k){
    sort(nums, numsSize);
    int i;
    for(i = 0; i < numsSize;i++) {
        if(nums[i] < 0 && k >0) {
            nums[i] = ~nums[i] + 1;
            k--;    
        }
    }
    if(k%2)
        nums[numsSize-1] = ~nums[numsSize-1] + 1;

    int ans = 0;
    for(i = 0; i < numsSize; i++) {
        ans+=nums[i];
    }
    return ans;
}

注：这里用其他的sort方法会更快