Flip-Karten, um die maximale Summe zu erhalten

Question

Bei N Karten, bei denen die i-Karte die Nummer x auf der Vorderseite hat, dann -x auf der Rückseite und eine einzige Operation, die nur einmal ausgeführt werden kann in aufeinanderfolgender Reihenfolge nur einmal.

Jetzt müssen wir Karten so drehen, dass die Summe der Anzahl der Kartenoberseiten maximal ist.

Beispiel: Wenn N = 5 und cards [] be {-2,3, -1, -4, -2} dann ist die Antwort 8, da wir die letzten 3 Karten umdrehen können, um die Konfiguration zu erhalten {-2,3 , 1,4,2} die Summe bis 8.

Mein Ansatz:

Go für jede mögliche Art und Weise für jede i-te Position als Startposition und finden die maximum.But ist ihr jede bessere Lösung für dieses Problem?

Mein Code: Bin nicht in der Lage Problem

#include<bits/stdc++.h> 
using namespace std; 
int solve(std::vector<int> const & numbers) 
{ 
    int min_so_far = numbers[0], min_ending_here = numbers[0]; 
    size_t begin = 0; 
    size_t begin_temp = 0; 
    size_t end = 0; 
    for(size_t i = 1; i < numbers.size(); i++) 
    { 
      if(min_ending_here > 0) 
      { 
        min_ending_here = numbers[i]; 
        begin_temp = i; 
      } 
      else 
      { 
        min_ending_here += numbers[i]; 
      } 

      if(min_ending_here <= min_so_far) 
      { 
        min_so_far = min_ending_here; 
        begin = begin_temp; 
        end = i; 
      } 
    } 
    int sum=0; 
    for(int i=0;i<begin;i++){ 
     sum+=numbers[i]; 
    } 
    for(int i=begin;i<=end;i++){ 
     sum-=numbers[i]; 
    } 
    for(int i=end+1;i<numbers.size();i++){ 
     sum+=numbers[i]; 
    } 
    return sum; 

} 
int main(){ 
int n; 
cin>>n; 
vector<int> arr; 
for(int i=0;i<n;i++){ 
    int x; 
    cin>>x; 
    arr.push_back(x); 
} 

    cout<<solve(arr)<<"\n"; 
} 

Answer 1

Das einzige, was Sie ist die minimale Summe finden müssen, bis noch zu finden, die Sie mit aufeinander folgenden Zahlen bilden kann, und dann diejenigen kippen. In Ihrem Beispiel addieren sich die letzten drei Zahlen zu -7, und es gibt keinen anderen Satz von fortlaufenden Nummern, die eine niedrigere Summe haben, also macht das Umdrehen den Trick. Wenn die Mindestsumme nicht negativ ist, müssen Sie sie nicht umdrehen.

Nun, was ich oben beschrieben ist ein gut bekannter Algorithmus, und es heißt Kadane's algorithm, die in O (n) gelöst werden kann, beachten Sie, dass der Wikipedia-Link zeigt, wie es für das Maximum zu tun, aber Sie können leicht Ändere es, um das Minimum zu finden.