1005. Maximized array sum after K negations

Address ：

Power button https://leetcode-cn.com/problems/maximize-sum-of-array-after-k-negations/

subject ：

Give you an array of integers nums And an integer k , Modify the array as follows ：

Select a subscript i  And will nums[i] Replace with -nums[i] .
Repeating this process happens to k Time . You can select the same subscript multiple times i .

After modifying the array in this way , Returns an array of The maximum possible and .

Example 1：

Input ：nums = [4,2,3], k = 1 Output ：5 explain ： Select subscript 1 ,nums Turn into [4,-2,3] .

Example 2：

Input ：nums = [3,-1,0,2], k = 3 Output ：6 explain ： Select subscript (1, 2, 2) ,nums Turn into [3,1,0,2] .

Example 3：

Input ：nums = [2,-3,-1,5,-4], k = 2 Output ：13 explain ： Select subscript (1, 4) ,nums Turn into [2,3,-1,5,4] .

Tips ：

1 <= nums.length <= 104 -100 <= nums[i] <= 100 1 <= k <= 104

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/maximize-sum-of-array-after-k-negations
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Ideas ：

There are several situations to consider ：

1. Totally positive number

        If k Is odd , Then turn it over 1 Time minimum value

        If k It's even , Don't consider flopping

2. Total negative number

        If k Less than or equal to negative number , Then put the k Negative flops

        If k More than a negative number , Then consider all negative numbers after flopping The rest k Parity

                The remaining k Is odd , Then turn the last number

                The remaining k yes even numbers , Don't consider flopping

3. There are positive and negative

         If k Less than or equal to negative number , Then put the k Negative flops

        If k More than a negative number , Then it means that all negative numbers become positive , Consider the rest k Parity

                The remaining k Is odd , The last negative number represents a positive number , Compare with the first positive number , That flip that

                The remaining k It's even , Don't consider flopping

Combine so many conditions , So the code is a little verbose .

The back is improved , Don't consider so much for the time being , as long as k When it can be covered (k>0), When you meet a negative number, you flip , Over k--

The process of looping all elements （ After the change ） Add up

Then we will deal with the situation whether it needs to be judged

If k There are residues and odd numbers ：

        The previous cycle will record the first positive number index

        If index Still initial , Indicates that the entire array is all negative , We need to subtract the value of the last element * 2

        If index by 0, Indicates that the entire array is positive , We need to subtract the first element * 2

        Other cases indicate that the array has positive and negative , Need to determine The value of a negative number at the boundary of a positive number is that small , Subtract its value * 2

        It's all about subtracting *2, Because it has been added once in the cycle , So remove the added value , Remove the last value to turn

Method 1 、 List various conditions

int cmp(const void *a, const void *b)
{
	return *(int *)a - *(int *)b;
}

int largestSumAfterKNegations(int* nums, int numsSize, int k){
	int i;
	int sum = 0;
	int negnum = 0;
	int idx = -1;
	
	qsort(nums, numsSize, sizeof(int), cmp);
	
	if(nums[0] > 0)
	{
		if(k & 1)
			nums[0] = 0 - nums[0];
	}
	else
	{
		for(i=0; i<numsSize; i++)
		{
			if(nums[i] < 0)
				negnum++;
			else
			{
				idx = i;
				break;
			}
		}
		
		if(negnum >= k)
		{
			i = 0;
			while(k--)
			{
				nums[i] = 0 - nums[i];
				i++;
			}
		}
		else if(negnum == 0)
		{
			if(k & 1)
				nums[0] = 0 - nums[0];
		}
		else
		{
			int k2 = k - negnum;
			
			i = 0;
			while(negnum--)
			{
				nums[i] = 0 - nums[i];
				i++;
			}
			
			if(idx == -1)
			{
				if(k2 & 1)
					nums[numsSize-1] = 0 - nums[numsSize-1];
			}
			else
			{
				if(k2 & 1)
				{
					//printf("nums[%d]=%d, nums[%d]=%d\n", idx-1, nums[idx-1], idx, nums[idx]);
					if(nums[idx-1] <= nums[idx])
						nums[idx-1] = 0 - nums[idx-1];
					else
						nums[idx] = 0 - nums[idx];
				}
			}
		}
	}
	
	for(i=0; i<numsSize; i++)
	{
		sum += nums[i];
	}
	
	return sum;
}

Method 2 、 Accumulate first and then determine the conditions

int cmp(const void *a, const void *b)
{
	return *(int *)a - *(int *)b;
}

int largestSumAfterKNegations(int* nums, int numsSize, int k){
	int i;
	int sum = 0;
	int idx = -1;
	
	qsort(nums, numsSize, sizeof(int), cmp);
	
	for(i=0; i<numsSize; i++)
	{
		if(idx == -1 && nums[i] >= 0)
			idx = i;
			
		if(k > 0 && nums[i] < 0)
		{
			nums[i] = 0 - nums[i];
			k--;
		}
		
		//printf("sum=%d + nums[%d]=%d, k=%d\n", sum, i, nums[i], k);
		sum += nums[i];
	}
	
    //printf("k=%d, idx=%d, sum=%d\n", k, idx, sum);
	if( (k > 0) && (k & 1) )
	{
		if(idx == -1)
			sum -= nums[numsSize-1] * 2;
		else if(idx == 0)
			sum -= nums[idx] * 2;
		else 
		{
			if(nums[idx-1] < nums[idx])
				sum -= nums[idx-1] * 2;
			else
				sum -= nums[idx] * 2;
		}
	}
	
	return sum;
}

See more brush notes