postgresql 遍历字符串数组_每日一道编程题（348）：1005.K次取反后最大化的数组和...

1005.K次取反后最大化的数组和

每日编程中遇到任何疑问、意见、建议请公众号留言或直接撩Q474356284(备注每日编程)

给定一个整数数组 A，我们只能用以下方法修改该数组：我们选择某个个索引i并将A[i]替换为-A[i]，然后总共重复这个过程K次。(我们可以多次选择同一个索引i。)

以这种方式修改数组后，返回数组可能的最大和。

示例 1：

输入：A = [4,2,3], K = 1输出：5解释：选择索引 (1,) ，然后 A 变为 [4,-2,3]。

示例 2：

输入：A = [3,-1,0,2], K = 3输出：6解释：选择索引 (1, 2, 2) ，然后 A 变为 [3,1,0,2]。

示例 3：

输入：A = [2,-3,-1,5,-4], K = 2输出：13解释：选择索引 (1, 4) ，然后 A 变为 [2,3,-1,5,4]。

提示：

1 <= A.length <= 10000

1 <= K <= 10000

-100 <= A[i] <= 100

解决方法：

(1)算法的基本思想：

算法一：

只要K未减为0，每次都找到数组的最小值，将其取反，最后求和。

算法二：

对数组从大至小排序，遍历数组。

如果当前数组元素大于0，则加至res

如果当前数组元素小于0，

K大于0，则取反，加至res中

K小于等于0，直接加至res中

遍历完数组后对K进行判断，如果K为奇数，则res需要减去最后一个元素(最小值)的2倍。

(注：比如4,3,2数组，K = 1，res = 4+3+2，如果K为偶数，我们可以将2取反变成-2，再取反变成2，但是如果K为奇数，我们总要将数组中的其中一个数取反，而在遍历数组的过程中，我们遇到正的就加起来了，并未取反，所以最后需要减掉最小值的2倍)

(2)代码实现：

classSolution

{

public:

intlargestSumAfterKNegations(vector<int>&A,intK){

while(K--)

{

autosmallest=min_element(begin(A),end(A));

(*smallest)*=-1;

}

returnaccumulate(A.begin(),A.end(),0);

}

};

classSolution

{

public:

intlargestSumAfterKNegations(vector<int>&A,intK){

sort(A.begin(),A.end(),[](inta,intb){returnabs(a)>abs(b);});

intres=0;

for(intele:A)

{

if(ele>=0)

res+=ele;

else

K>0?res+=-ele,K--:res+=ele;

}

//res=x+abs(s)==>whatwewantisres=x-abs(s),so:

if(K%2)

res-=2*abs(A.back());

returnres;

}

};

明日预告：中南大学上机题(一)

大家都很关心考试的难易程度。K老师出题有一个规律，在出题之前，他会随机写下一个字符串，只要在这个字符串中能按顺序找到E，A，S，Y四个字母，他出题就会比较简单。你拿到了字符串，请你告诉别人题目难不难吧。

输入格式：

输入的数据有多组，每组占一行，由一个字符串组成(字符串的长度不超过1000)。

输出格式：

输入样例：

eAsy

SEoAtSNY

输出样例：

difficult

easy