Առավելագույնի հասցնել զանգվածի գումարը K Negations Leetcode Solution- ից հետո


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Amazon
Դասավորություն LeetCode

Այս գրառումը Maximize Sum Of Array- ում է K Negations Leetcode Solution- ից հետո

Խնդրի հայտարարություն

Խնդրի մեջ »Առավելագույնի հասցնել զանգվածի զանգվածը K- ից հետո Բացասականություններ”Մեզ տրված է զանգվածի ar և մեծություն K. Theանգվածը բաղկացած է ամբողջ արժեքներից: Մենք կարող ենք arr [i] արժեքը փոխել –arr [i] K անգամ: Մենք կարող ենք կրկնել i- ի արժեքը: Մեր խնդիրն է առավելագույնի հասցնել զանգվածի գումարը `կիրառելով այս մեթոդը K անգամ, և փոփոխումից հետո վերադարձնել զանգվածի ընդհանուր գումարը:

Օրինակ

arr = [2,-3,-1,5,-4], k=2
13

Բացատրությունը.

Առավելագույնի հասցնել զանգվածի գումարը K Negations Leetcode Solution- ից հետո

Տրված զանգվածում, երբ մենք փոխարինելու ենք -3-ից 3-ին և -4-ից 4-ին, ապա զանգվածի ընդհանուր գումարը դառնում է 13:

Մոտեցում

Մեր խնդիրն է առավելագույնի հասցնել զանգվածի գումարը և զանգվածը բաղկացած է և՛ դրական, և՛ բացասական տարրերից, ուստի մենք հետևելու ենք հետևյալ քայլերին.

  1. Առաջին հերթին մենք տեսակավորելու ենք զանգվածը, քանի որ ուզում ենք փոխել ամենափոքր արժեքի նշանը: Սա օգտակար կլինի առավելագույնի հասցնելու համար զանգվածի գումար.
  2.  Այժմ մենք կփոխենք առավելագույնը K- ի նշանը բացասական թվեր.
  3. Միևնույն ժամանակ, մենք նաև հետևելու ենք, թե զրոյն առկա է զանգվածում, թե ոչ:
  4. Գտնել զանգվածի գումար.
  5. Մեր վերջնական պատասխանը կլինի զանգվածի գումար եթե:
    1. K– ի արժեքը դառնում է զրո:
    2. Eroրոյը առկա է զանգվածում: Այս կերպ մենք կշարունակենք փոխել զրոյի նշանը:
    3. K- ի արժեքը բացասական արժեքների նշանը փոխելուց հետո հավասար է: Այսպիսով, մենք դրական թիվը կդարձնենք բացասական թվին և այնուհետև կդարձնենք այն կրկին դրական:
  6. Այստեղ K- ի արժեքը բացասական է, ուստի մենք կփոխենք նշանի նշանը ամենափոքր դրական թիվը Կ անգամներ: Դա կդարձնի այն բացասական: Այժմ մենք կվերադարձնենք զանգվածի նոր գումարը:

Neանգվածի գումարը առավելագույնի հասցնելու կոդ K Negations Leetcode լուծումից հետո

C ++ ծածկագիր

#include <bits/stdc++.h> 
using namespace std; 
    int largestSumAfterKNegations(vector<int>& A, int K) {
        sort(A.begin(),A.end());
        int sum=0,neg=0,zero=0;
        for(int i=0;i<A.size();i++)
        {
            if(A[i]==0)
                zero=1;
            if(A[i]<0&&K>0)
            {  A[i]=-A[i];K--;}
            sum+=A[i];
        }
        if(zero||K==0||K%2==0)
         return sum;
        else
            return sum-2*(*min_element(A.begin(),A.end()));       
    }
int main() 
{ 
 vector<int> arr = {2,-3,-1,5,-4}; 
 int k=2;
 cout<<largestSumAfterKNegations(arr,k)<<endl; 
 return 0;
}
13

Java կոդ

import java.util.Arrays; 
public class Tutorialcup {
    public static int largestSumAfterKNegations(int[] A, int K) {
        Arrays.sort(A);
        int sum=0,neg=0,zero=0;
        for(int i=0;i<A.length;i++)
        {
            if(A[i]==0)
                zero=1;
            if(A[i]<0&&K>0)
            {  A[i]=-A[i];K--;}
            sum+=A[i];
        }
        if(zero==1||K==0||K%2==0)
         return sum;
        else
            return sum-2*(Arrays.stream(A).min().getAsInt());      
    }
  public static void main(String[] args) {
    int [] arr = {2,-3,-1,5,-4}; 
    int k=2;
    int ans=  largestSumAfterKNegations(arr,k);
    System.out.println(ans);
  }
}
13

Neանգվածի առավելագույն գումարի բարդության վերլուծություն K ժխտումների Leetcode լուծումից հետո

Timeամանակի բարդությունը

Վերոնշյալ ծածկագրի ժամանակի բարդությունն է O (n) քանի որ մենք տրված զանգվածը միայն մեկ անգամ ենք անցնում:

Տիեզերական բարդություն

Վերոնշյալ ծածկագրի տիեզերական բարդությունն է Ո (1) քանի որ մենք պատասխաններ պահելու համար օգտագործում ենք միայն փոփոխական:

Սայլակ