当前位置:网站首页>1005. Maximized array sum after K negations
1005. Maximized array sum after K negations
2022-07-06 16:07:00 【mrbone9】
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;
}
边栏推荐
- 7-1 懂的都懂 (20 分)
- 渗透测试 ( 2 ) --- 渗透测试系统、靶机、GoogleHacking、kali工具
- Opencv learning log 33 Gaussian mean filtering
- Frida hook so layer, protobuf data analysis
- Opencv learning log 29 -- gamma correction
- Opencv learning log 12 binarization of Otsu method
- Research Report of exterior wall insulation system (ewis) industry - market status analysis and development prospect prediction
- PySide6 信号、槽
- [exercise-6] (UVA 725) division = = violence
- Opencv learning log 13 corrosion, expansion, opening and closing operations
猜你喜欢
渗透测试 2 --- XSS、CSRF、文件上传、文件包含、反序列化漏洞
7-1 懂的都懂 (20 分)
Penetration testing (5) -- a collection of practical skills of scanning King nmap and penetration testing tools
1010 things that college students majoring in it must do before graduation
信息安全-威胁检测-flink广播流BroadcastState双流合并应用在过滤安全日志
【练习-4】(Uva 11988)Broken Keyboard(破损的键盘) ==(链表)
Penetration test (2) -- penetration test system, target, GoogleHacking, Kali tool
b站 實時彈幕和曆史彈幕 Protobuf 格式解析
Essai de pénétration (1) - - outils nécessaires, navigation
Ball Dropping
随机推荐
Socket communication
Auto. Getting started with JS
栈的经典应用—括号匹配问题
[exercise-7] (UVA 10976) fractions again?! (fraction split)
Opencv learning log 31 -- background difference
Programmers, what are your skills in code writing?
Opencv learning log 14 - count the number of coins in the picture (regardless of overlap)
Find 3-friendly Integers
[exercise -11] 4 values why sum is 0 (and 4 values of 0)
【练习-2】(Uva 712) S-Trees (S树)
b站 实时弹幕和历史弹幕 Protobuf 格式解析
信息安全-威胁检测引擎-常见规则引擎底座性能比较
Penetration test (3) -- Metasploit framework (MSF)
Opencv learning log 32 edge extraction
Opencv learning log 16 paperclip count
China's peripheral catheter market trend report, technological innovation and market forecast
The concept of C language array
Ball Dropping
Perform general operations on iptables
对iptables进行常规操作