लाभ को अधिकतम करना उद्धरण

Question

मैं इस सवाल का एक स्टार्टअप के लिए साक्षात्कार, जबकि कहा गया था और

Code Sprint:systems

** सवाल पर हाल ही में प्रतियोगिता में फिर से देखा:

आप दिए गए हैं दिनों के एक सेट के लिए स्टॉक की कीमतें। प्रत्येक दिन, आप या तो स्टॉक की एक इकाई खरीद सकते हैं, किसी भी स्टॉक यूनिट को बेच सकते हैं जिसे आपने पहले से खरीदा है, या कुछ भी नहीं। क्या अधिकतम लाभ आप अपने ट्रेडिंग रणनीति बेहतर योजना बना द्वारा प्राप्त कर सकते हैं? **

उदाहरण (इनपुट यानी दिन का कोई भिन्न हो सकते हैं)

5 3 2 => लाभ = 0 // के बाद से मूल्य प्रत्येक दिन कम हो जाती है, अधिकतम लाभ हम = 0

1 2 100 => लाभ = 197

1 3 1 2 => लाभ = 3 // हम 3 में 1 बेचने पर खरीद, तो हम खरीदने के लिए कर सकते हैं 1 पर और 2 पर बेचते हैं .. कुल लाभ = 3

मेरा समाधान:

ए) उस दिन को खोजें जब स्टॉक मूल्य सबसे बड़ा था। उस दिन तक स्टॉक की 1 इकाई खरीदते रहें।

ख) यदि उस दिन है अंतिम दिन तो छोड़ दिया:

बाकी

: उस दिन सभी स्टॉक बेचें और उस दिन के बाद सरणी विभाजित है और शेष तत्वों पर recurse
ग) लाभ विलय

उदाहरण 1 4 1 2 3
ए) दिन 2 पर उच्चतम स्टॉक मूल्य .. इसलिए हम दिन 1 पर स्टॉक खरीदते हैं और इसे दिन 2 (लाभ = 3) पर बेचते हैं तो हम शेष दिनों पर पुन: कार्य करते हैं: 1 2 3

बी) अधिकतम मूल्य 3 है (दिन में 5) तो हम दिन 3 और 4 दिन पर शेयर खरीदने और 5 दिन पर बेचने रखना (लाभ = (3 * 2 - 3 = 3)

ग) कुल लाभ = 3 + 3 = 6

जटिलता इसके लिए ओ (एन^2) हो जाता है। इस समाधान ने 11 मामलों में से 10 को पारित किया लेकिन अंतिम परीक्षण मामले (यानी सबसे बड़ा इनपुट) पर समय सीमा पार हो गई।

तो मेरा सवाल यह है कि क्या कोई इस समस्या के लिए एक अधिक कुशल समाधान के बारे में सोच सकता है? क्या कोई गतिशील प्रोग्रामिंग समाधान है?

पीएस: यह पहली बार है कि मैं यहां एक प्रश्न पूछ रहा हूं। इसलिए कृपया मुझे बताएं कि मुझे इस प्रश्न में चीजों को सुधारने/जोड़ने की आवश्यकता है

Answer 1

मैं आपकी विधि के तर्क से सहमत हूं लेकिन पुनरावर्ती प्रसंस्करण या वैश्विक अधिकतम खोजों की आवश्यकता नहीं है। बिक्री/खरीद के दिनों को खोजने के लिए आपको केवल एक बार प्रत्येक दिन देखने की आवश्यकता है:

चाल अंत से शुरू करना है। स्टॉक व्यापार आसान है यदि आपकी यात्रा समय पर पीछे की ओर है!

अगर आपको लगता है कोड आसान है शब्दों से पढ़ने के लिए, बस अपना स्पष्टीकरण को छोड़, लेकिन यहाँ जाता है:

छोर से पढ़ना, उस दिन की कीमत को देखो। क्या यह अब तक की सबसे ज्यादा कीमत है (अंत में), फिर बेचो! अंतिम दिन (जहां हम पढ़ना शुरू करते हैं) आप हमेशा बेचेंगे।

फिर अगले दिन जाएं (याद रखें, समय में पीछे की ओर)। क्या अब तक यह सबसे ज्यादा कीमत है (हमने अभी तक देखा है)? - फिर सब बेच दो, आपको एक बेहतर दिन नहीं मिलेगा। अन्यथा कीमतें बढ़ती हैं, इसलिए खरीदें। शुरुआत तक उसी तरह जारी रखें।

पूरी समस्या एक एकल रिवर्स लूप के साथ हल की गई है: व्यापार के निर्णयों और लाभ दोनों की गणना करना।

यहाँ सी की तरह अजगर में कोड है: (मैं सबसे pythonic सामान बचा एक सी व्यक्ति के लिए पठनीय होना चाहिए।)

def calcprofit(stockvalues): 
    dobuy=[1]*len(stockvalues) # 1 for buy, 0 for sell 
    prof=0 
    m=0 
    for i in reversed(range(len(stockvalues))): 
     ai=stockvalues[i] # shorthand name 
     if m<=ai: 
      dobuy[i]=0 
      m=ai 
     prof+=m-ai 
    return (prof,dobuy) 

उदाहरण:

calcprofit([1,3,1,2]) gives (3, [1, 0, 1, 0]) 
calcprofit([1,2,100]) gives (197, [1, 1, 0]) 
calcprofit([5,3,2]) gives (0, [0, 0, 0]) 
calcprofit([31,312,3,35,33,3,44,123,126,2,4,1]) gives 
(798, [1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0]) 

ध्यान दें कि m सबसे अधिक है स्टॉक मूल्य हमने देखा है (अंत से)। यदि ai==m तो चरण में खरीदे गए स्टॉक से लाभ 0 है: उस बिंदु के बाद हमारे पास घटती या स्थिर कीमत थी और उसने नहीं खरीदा। प्रत्येक तत्व के लिए पूर्व प्रसंस्करण में
,:

आप सत्यापित कर सकते हैं कि लाभ गणना एक सरल पाश के साथ सही है

stock=0 
money=0 
for i in range(len(stockvalues)): 
    if dobuy[i]: 
     stock+=1 
     money-=stockvalues[i] 
    else: 
     money+=stockvalues[i]*stock 
     stock=0 
print("profit was: ",money) 

Answer 2

एक और तरीका है इस पर गौर करने के लिए (सादगी के लिए यह ऊपर समारोह के भीतर है की कल्पना) a[i]a[j] सेंट खोजें j > i और यह (a[j] - a[i])
तो अधिकतम, बेस्ट आप a[i] पर एक मूल्य के लिए क्या कर सकते हैं a[i] पर खरीदें और a[j] पर बेचें। यदि कोई a[j] s.t मौजूद नहीं है। a[j] > a[i] फिर a[i] बिल्कुल खरीदें नहीं है।

Preprocessing समय: O(N)

S[N-1] = A[N-1]; 
for(int i=N-2; i>=0; --i) 
     S[i] = max(A[i], S[i+1]); 

यहाँ, एस [i] कीमत, जिस पर आप बेचना चाहिए एक [i] है।

कुल लाभ संक्षेप: O(N)

long long int Profit = 0; 
    for(int i=0;i<N;++i) 
      Profit += max(0, (S[i]-A[i])); 

Answer 3

अपने तर्क सही है ... वैश्विक maxima's..but प्रत्यावर्तन की आवश्यकता नहीं है पर

बेचने ...

ith तत्व अगर वैश्विक maxima है ... मैं पहले से सभी स्टॉक बेचते हैं!

अब समस्या पिछले जवाब + i + 1 एन करने के लिए करने के लिए कम कर देता है ...

प्रत्यावर्तन की आवश्यकता नहीं है ... रैखिक गणना कर सकते हैं!

Answer 4

मैंने बस एक प्रतियोगिता साइट में उस समस्या को हल किया। मुझे लगता है कि स्वीकार्य उत्तर से मुझे एक सरल एल्गोरिदम मिला है।

1. smax = maximum stock price from the list 
2. then find the profit by assuming you have bought all the stocks till smax 
    and you sell it at the price of smax 
3. then check if smax is the last element of the stock price list 
    if yes then return profit as answer, 
    if no 
    then make a new list containing stock prices after smax to the last stock price 
    and repeat steps 1-3 and keep adding profit of each iteration to get the final profit. 

Answer 5

सरणी के अंत से 0.Start ताकि recurse करने की कोई जरूरत
1. smax = सूची
2.Then से अधिकतम शेयर की कीमत यह सोचते हैं आप जब तक सभी स्टॉक खरीदा है से लाभ पाते हैं smax और आप smax

  public static void main(String[] args) { 

      Scanner sc = new Scanner(System.in); 
      int numOfTestCase = sc.nextInt(); 
      for (int i = 0; i < numOfTestCase; i++) { 
       int n = sc.nextInt(); 
       long profit = 0; 
       int[] stockPrice = new int[n]; 

       for (int j = 0; j < n; j++) { 
         stockPrice[j] = sc.nextInt(); 
       } 

       int currMax = Integer.MIN_VALUE; 

       for (int j = n - 1; j >= 0; j--) { 
         if (currMax < stockPrice[j]) { 
           currMax = stockPrice[j]; 
         } 
         profit += (currMax - stockPrice[j]); 
       } 
       System.out.println(profit); 


      } 
    } 

Answer 6

मेरे तर्क है की कीमत पर इसे बेचने, आप हर शेयर के लिए लाभ अधिकतम शेयर की कीमत से पहले खरीदा हो। विचार की इस पंक्ति का उपयोग करके, आप अधिकतम मूल्य से पहले हर स्टॉक खरीदते हैं, इसे अधिकतम पर बेचते हैं, और शेष स्टॉक कीमतों के लिए एक ही चीज़ दोहराते हैं।

function profit(prices){ 
    var totalStocks = 0, profitMade = 0; 

    var buySell = function(sortedPrices){ 
     for(var i = 0, len = sortedPrices.length; i < len; i++){ 
      if (i < len - 1){ 
       totalStocks++; 
       profitMade = profitMade - sortedPrices[i]; 
      }else{ 
       profitMade = profitMade + totalStocks * sortedPrices[i]; 
       totalStocks = 0; 
      } 
     } 
    }, splitMaxPrice = function(rawPrices){ 
     var leftStocks = rawPrices.splice(rawPrices.lastIndexOf(Math.max.apply(null, rawPrices))+1); 
     buySell(rawPrices); 
     if(leftStocks.length > 0){ 
      splitMaxPrice(leftStocks); 
     } 
     return; 
    }; 

    splitMaxPrice(prices); 

    return profitMade; 

} 

Answer 7

इस कार्य के लिए एक और हे (एन) समाधान स्थानीय न्यूनतम और अधिकतम अधिकतम और न्यूनतम के बीच सबसे अच्छा सम्मान (लाभ) जानते हुए भी कि अधिकतम अधिक से अधिक सूचकांक तो मिनट होनी चाहिए खोजने का उपयोग करके किया जा सकता है। हमें पिछले सर्वोत्तम स्थानीय मिनट (सी # कार्यान्वयन) को भी देखने की जरूरत है।

public int[] GetBestShareBuyingStrategy(int[] price) 
    { 
     var n = price.Length; 
     if (n <= 1) 
      return null; 

     var profit = 0; 
     var min = 0; 
     var max = 0; 
     var lmin = 0; 

     for (var i = 1; i < n; i++) 
     { 
      var lmax = i; 
      var lp = price[lmax] - price[lmin]; 
      if (lp <= 0) 
      { 
       lmin = i; 
      } 
      else 
      { 
       var tp = price[lmax] - price[min]; 
       if (lp > tp && lp > profit) 
       { 
        min = lmin; 
        max = lmax; 
        profit = lp; 
       } 
       else if (tp > profit) 
       { 
        max = lmax; 
        profit = tp; 
       } 
      } 
     } 

     return profit > 0 
      ? new [] {min, max} 
      : null; 
    } 



    [Test] 
    [TestCase(new[] { 10, 9, 8, 7, 3 })] 
    [TestCase(new[] { 5, 5, 5, 5, 5 })] 
    [TestCase(new[] { 5, 4, 4, 4 })] 
    [TestCase(new[] { 5, 5, 3, 3 })] 
    public void GetBestShareBuyingStrategy_When_no_sense_to_buy(int[] sharePrices) 
    { 
     var resultStrategy = GetBestShareBuyingStrategy(sharePrices); 
     Assert.IsNull(resultStrategy); 
    } 

    [Test] 
    [TestCase(new[] { 10, 8, 12, 20, 10 }, 1, 3)] 
    [TestCase(new[] { 5, 8, 12, 20, 30 }, 0, 4)] 
    [TestCase(new[] { 10, 8, 2, 20, 10 }, 2, 3)] 
    [TestCase(new[] { 10, 8, 2, 20, 10 }, 2, 3)] 
    [TestCase(new[] { 10, 2, 8, 1, 15, 20, 10, 22 }, 3, 7)] 
    [TestCase(new[] { 1, 5, 2, 7, 3, 9, 8, 7 }, 0, 5)] 
    [TestCase(new[] { 3, 5, 2, 7, 3, 9, 8, 7 }, 2, 5)] 
    public void GetBestShareBuyingStrategy_PositiveStrategy(int[] sharePrices, int buyOn, int sellOn) 
    { 
     var resultStrategy = GetBestShareBuyingStrategy(sharePrices); 
     Assert.AreEqual(buyOn, resultStrategy[0]); 
     Assert.AreEqual(sellOn, resultStrategy[1]); 
    } 

Answer 8

यहां अधिक सरल और समझने में आसान है;

private static void BuyOnceAndSellONce() 
    { 
     int[] stock = new int[] { 100, 180, 260, 310, 40, 535, 695 }; 
     int profit = 0; 
     int minimumPrice = int.MaxValue; 
     for (int i = 0; i < stock.Length; i++) 
     { 
      profit = Math.Max(profit, stock[i] - minimumPrice); 
      minimumPrice = Math.Min(stock[i], minimumPrice); 

     } 
     Console.WriteLine("profit " + profit); 
    } 

    private static void MultipleBuySellButNonOverlappingTransactions() 
    { 
     int[] stock = new int[] { 100, 180, 260, 310, 40, 535, 695 }; 
     int totalProfit = 0; 
     int currentProfit = 0; 
     for (int i = 1; i < stock.Length;i++) 
     { 
      currentProfit = stock[i] - stock[i - 1]; 
      if (currentProfit > 0) 
       totalProfit += currentProfit; 
     } 

     Console.WriteLine(totalProfit); 
    }