მასივის ჯამის მაქსიმიზაცია K Negations Leetcode Solution- ის შემდეგ


Რთული ტური Easy
ხშირად ეკითხებიან Amazon
Array LeetCode

ეს პოსტი მოცემულია მასივის მაქსიმალურად გაზრდაზე და K Negations Leetcode Solution– ის შემდეგ

პრობლემის განცხადება

In the problem ”Array მასივის მაქსიმალურად გაზრდა K– ს შემდეგ უარყოფა”მოცემულია მასივი arr და მნიშვნელობა K. მასივი შედგება მთელი მნიშვნელობებისგან. Arr [i] მნიშვნელობის შეცვლა შეგვიძლია -arr [i] K ჯერ. შეგვიძლია გავიმეოროთ i- ის მნიშვნელობა. ჩვენი ამოცანაა, მასივის ჯამი მაქსიმალურად გავზარდოთ ამ მეთოდის K დროის გამოყენებით და მასივის ჯამი დავუბრუნოთ მოდიფიკაციის შემდეგ.

მაგალითი

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

განმარტება:

მასივის ჯამის გაზრდა K უარყოფის შემდეგ Leetcode Solution

მოცემულ მასივში, როდესაც შევცვლით -3-დან 3-მდე და -4-დან 4-მდე, მასივის მთლიანი ჯამი ხდება 13.

მიდგომა

ჩვენი ამოცანაა მასივის ჯამის მაქსიმიზაცია და მასივი შედგება როგორც დადებითი, ასევე უარყოფითი ელემენტებისგან, ასე რომ, ჩვენ მივყვებით შემდეგ ნაბიჯებს:

  1. უპირველეს ყოვლისა ჩვენ დავალაგებთ მასივს, რადგან გვინდა შევცვალოთ უმცირესი მნიშვნელობის ნიშანი. ეს გამოდგება მაქსიმალური მნიშვნელობით მასივი ჯამი.
  2.  ახლა ჩვენ შევცვლით მაქსიმუმ K ნიშანს უარყოფითი რიცხვები.
  3. ამასობაში ჩვენ ასევე გავაგრძელებთ თვალყურს, არის ნულოვანი მასივი თუ არა.
  4. მოძებნა მასივი ჯამი.
  5. ჩვენი საბოლოო პასუხი იქნება მასივი ჯამი თუ:
    1. K– ის მნიშვნელობა ხდება ნულოვანი.
    2. ნულოვანი მასივშია. ამ გზით ჩვენ განვაგრძობთ ნულის ნიშნის შეცვლას.
    3. უარყოფითი მნიშვნელობების ნიშნის შეცვლის შემდეგ K– ის მნიშვნელობის ტოლია. ამ გზით ჩვენ პოზიტიურ რიცხვს დავდებთ უარყოფით რიცხვზე და შემდეგ კვლავ გავაკეთებთ პოზიტიურს.
  6. აქ K– ის მნიშვნელობა უარყოფითია, ამიტომ ჩვენ შევცვლით ნიშნის ნიშანს ყველაზე მცირე დადებითი რიცხვი K ჯერ. ეს მას უარყოფითად აქცევს. ახლა ჩვენ დავაბრუნებთ მასივის ახალ თანხას.

K მასივის მაქსიმალური გასადიდებლად კოდი K უარყოფის შემდეგ Leetcode Solution

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

ჯავის კოდი

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

მასივის მაქსიმალური ჯამის სირთულის ანალიზი K უარყოფის შემდეგ Leetcode Solution

დროის სირთულე

ზემოთ მოცემული კოდის სირთულეა O (n) რადგან ჩვენ მხოლოდ ერთხელ გავდივართ მოცემულ მასივს.

კოსმოსური სირთულის

ზემოთ მოცემული კოდის სივრცის სირთულეა O (1) რადგან პასუხების შესანახად ვიყენებთ მხოლოდ ცვლადს.

ლიტერატურა