Μεγιστοποιήστε το άθροισμα της σειράς μετά από το K Negations Leetcode Solution


Επίπεδο δυσκολίας Εύκολος
Συχνές ερωτήσεις αμαζόνα
Παράταξη LeetCode

Αυτή η ανάρτηση είναι στο Maximize Sum Of Array After K Negations Leetcode Solution

Δήλωση προβλήματος

Στο πρόβλημα "Μεγιστοποιήστε το άθροισμα της σειράς μετά το Κ Αρνήσεις"Μας δίνεται ένας πίνακας arr και μια τιμή K. Ο πίνακας αποτελείται από ακέραιες τιμές. Μπορούμε να αλλάξουμε την τιμή του 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. η τιμή του Κ γίνεται μηδέν.
    2. Το μηδέν υπάρχει στον πίνακα. Με αυτόν τον τρόπο θα συνεχίσουμε να αλλάζουμε το σύμβολο του μηδέν.
    3. Η επανακαθορισμένη τιμή του K μετά την αλλαγή του σημείου αρνητικών τιμών είναι ομοιόμορφη. Με αυτόν τον τρόπο θα κάνουμε έναν θετικό αριθμό σε έναν αρνητικό αριθμό και μετά θα τον κάνουμε ξανά θετικό.
  6. Εδώ η τιμή του Κ είναι αρνητική, οπότε θα αλλάξουμε το σύμβολο του μικρότερος θετικός αριθμός Κ φορές. Αυτό θα το κάνει αρνητικό. Τώρα θα επιστρέψουμε το νέο άθροισμα του πίνακα.

Κωδικός για τη μεγιστοποίηση του αθροίσματος της σειράς μετά από K Negations 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

Κωδικός 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

Ανάλυση πολυπλοκότητας της μεγιστοποίησης του αθροίσματος της σειράς μετά από K Negations Leetcode Solution

Χρόνος πολυπλοκότητας

Η χρονική πολυπλοκότητα του παραπάνω κώδικα είναι O (n) γιατί διασχίζουμε τον δεδομένο πίνακα μόνο μία φορά.

Διαστημικότητα

Η πολυπλοκότητα του παραπάνω κώδικα είναι Ο (1) γιατί χρησιμοποιούμε μόνο μια μεταβλητή για την αποθήκευση απαντήσεων.

αναφορές