फ्लिप कार्ड अधिकतम राशि

Question

को देखते हुए एन कार्ड प्राप्त करने के लिए करता है, तो ith कार्ड अपने सामने की ओर संख्या एक्स है तो यह पीछे की ओर -x और एक ही आपरेशन है कि केवल कि कार्ड के किसी भी संख्या फ्लिप करने के लिए है एक बार किया जा सकता है होगा जहां केवल एक बार लगातार आदेश में।

अब हम इस तरह से ताश के पत्तों की ऊपरी चेहरे की संख्या की उस राशि अधिकतम है में कार्ड फ्लिप करने की जरूरत है।

उदाहरण: यदि एन = 5 और कार्ड [] हो {-2,3, -1, -4, -2} तो यहाँ जवाब 8 के रूप में हम पिछले 3 कार्ड फ्लिप विन्यास प्राप्त करने के लिए कर सकते हैं {-2,3 , 1,4,2} 8.

लिए जो राशि मेरे दृष्टिकोण:

प्रारंभ स्थिति के रूप में प्रत्येक ith पद के लिए प्रत्येक संभव तरीके के लिए जाओ और पाते हैं maximum.But इस समस्या के लिए अपने किसी भी बेहतर समाधान है?

मेरे कोड: अभी तक

#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

केवल एक चीज आप को खोजने की जरूरत कम से कम राशि है कि आप लगातार संख्या के साथ फार्म कर सकते हैं, और फिर उन फ्लिप है जब तक समस्या का पता लगाने में सक्षम नहीं हूँ। आपके उदाहरण में, अंतिम तीन संख्याएं -7 तक बढ़ती हैं, और लगातार संख्या का कोई अन्य सेट नहीं है जिसमें कम योग होता है, इसलिए उन्हें फ़्लिप करना चाल है। यदि न्यूनतम राशि गैर ऋणात्मक है, तो आपको उन्हें फ़्लिप करने की आवश्यकता नहीं है।

अब, जो मैंने ऊपर वर्णित किया है वह एक प्रसिद्ध एल्गोरिदम है, और इसे Kadane's algorithm कहा जाता है, जिसे ओ (एन) में हल किया जा सकता है, ध्यान दें कि विकिपीडिया लिंक दिखाता है कि अधिकतम के लिए इसे कैसे किया जाए, लेकिन आप आसानी से कर सकते हैं न्यूनतम खोजने के लिए इसे संशोधित करें।