കൂൾ‌ഡ own ൺ‌ ലീറ്റ്‌കോഡ് സൊല്യൂഷൻ ഉപയോഗിച്ച് സ്റ്റോക്ക് വാങ്ങാനും വിൽക്കാനുമുള്ള മികച്ച സമയം


വൈഷമ്യ നില മീഡിയം
പതിവായി ചോദിക്കുന്നു അഡോബി ആമസോൺ ഗോൾഡ്മാൻ സാക്സ് യാഹൂ
ഡൈനാമിക് പ്രോഗ്രാമിംഗ്

പ്രശ്നം പ്രസ്താവന

“കൂൾഡ own ൺ ഉപയോഗിച്ച് സ്റ്റോക്ക് വാങ്ങാനും വിൽക്കാനുമുള്ള മികച്ച സമയം” എന്ന പ്രശ്‌നത്തിൽ, അറേയിലെ ഓരോ ഘടകങ്ങളും ആ ദിവസം നൽകിയ സ്റ്റോക്കിന്റെ വില ഉൾക്കൊള്ളുന്ന ഒരു അറേ ഞങ്ങൾക്ക് നൽകിയിരിക്കുന്നു.

ഇടപാടുകളുടെ എണ്ണത്തിൽ നിയന്ത്രണമില്ല. ഇടപാടിന്റെ നിർവചനം സ്റ്റോക്കിന്റെ ഒരു പങ്ക് വാങ്ങുകയും സ്റ്റോക്കിന്റെ ഒരു പങ്ക് വിൽക്കുകയും ചെയ്യുക എന്നതാണ്.

ഇനിപ്പറയുന്ന നിയന്ത്രണങ്ങൾക്ക് കീഴിൽ പരമാവധി ലാഭം കണ്ടെത്തുക എന്നതാണ് ഞങ്ങളുടെ ചുമതല:

  1. മുമ്പത്തെ സ്റ്റോക്ക് ഞങ്ങൾ വിറ്റില്ലെങ്കിൽ ഞങ്ങൾക്ക് ഒരു പുതിയ സ്റ്റോക്ക് വാങ്ങാൻ കഴിയില്ല. അത് ഞങ്ങൾക്ക് ഒരു സ്റ്റോക്ക് പരമാവധി കൈവരിക്കാവുന്ന ഒരു സമയത്താണ്.
  2. ith ദിവസം ഞങ്ങൾ ഒരു സ്റ്റോക്ക് വിൽക്കുകയാണെങ്കിൽ (i + 1) th ആം ദിവസം സ്റ്റോക്ക് വാങ്ങാൻ കഴിയില്ല. അത് കൂൾഡ own ൺ കാലയളവിന്റെ 1 ദിവസമാണ്

ഉദാഹരണം

prices = [1,2,3,0,2]
3

വിശദീകരണം: ലഭിക്കുന്ന പരമാവധി ലാഭം 3. ഇടപാട് വിശദാംശങ്ങൾ ചുവടെ:

ആദ്യ ദിവസം: വാങ്ങുക

രണ്ടാം ദിവസം: വിൽക്കുക

മൂന്നാം ദിവസം: കൂൾഡൗൺ

നാലാം ദിവസം: വാങ്ങുക

അഞ്ചാം ദിവസം: വിൽക്കുക

കൂൾ‌ഡ own ൺ‌ ലീറ്റ്‌കോഡ് സൊല്യൂഷൻ ഉപയോഗിച്ച് സ്റ്റോക്ക് വാങ്ങാനും വിൽക്കാനുമുള്ള മികച്ച സമയത്തിനുള്ള സമീപനം

ഈ പ്രശ്നം പരിഹരിക്കുന്നതിന് ഞങ്ങൾ കുറച്ച് കാര്യങ്ങൾ ശ്രദ്ധിക്കേണ്ടതുണ്ട്:

  1. ഞങ്ങൾക്ക് ഒരു സ്റ്റോക്ക് വിൽക്കാൻ ആഗ്രഹിക്കുമ്പോഴെല്ലാം ഞങ്ങൾ നേരത്തെ സ്റ്റോക്ക് വാങ്ങിയിരിക്കണം. ഒരു സ്റ്റോക്ക് വിൽക്കുന്നതിനുള്ള മാർഗ്ഗം ഒരു സ്റ്റോക്ക് വാങ്ങുന്നതിനെ ആശ്രയിച്ചിരിക്കുന്നു.
  2. കൂൾഡൗൺ കാലയളവിന്റെ ഒരു ദിവസം നിർബന്ധമാണ്. അതിനാൽ ഒരു സ്റ്റോക്ക് വാങ്ങുന്നത് കൂൾഡ own ൺ കാലഘട്ടത്തെ ആശ്രയിച്ചിരിക്കുന്നു.

ഈ പോയിന്റുകൾ മനസ്സിൽ വച്ചുകൊണ്ട് നമുക്ക് സംസ്ഥാനങ്ങളെ നിർവചിക്കാം:

  • സ്റ്റേറ്റ്-എ: ഈ അവസ്ഥയിൽ, നമുക്ക് ഒരു സ്റ്റോക്ക് വാങ്ങാം അല്ലെങ്കിൽ വിശ്രമിക്കാം.
  • STATE-B: ഒരു സ്റ്റോക്ക് വാങ്ങിയ ശേഷം നമുക്ക് സ്റ്റോക്ക് വിൽക്കാം അല്ലെങ്കിൽ ബാക്കി എടുക്കാം.
  • STATE-C: ഇതൊരു തണുത്ത സംസ്ഥാനമാണ്. കൂൾ‌ഡ own ൺ‌ കാലയളവ് കഴിഞ്ഞാൽ‌ ഞങ്ങൾ‌ STATE-A ലേക്ക് നീങ്ങുന്നു.

കൂൾഡ own ൺ ഉപയോഗിച്ച് സ്റ്റോക്ക് വാങ്ങാനും വിൽക്കാനുമുള്ള മികച്ച സമയം

ഈ മൂന്ന് സംസ്ഥാനങ്ങൾ തമ്മിലുള്ള ബന്ധം ഒരു ആക്കി മാറ്റാം ബീജഗണിത പദപ്രയോഗം ഇവിടെ STATE-X [i] സംസ്ഥാന x ലെ ith ദിവസം വരെ പരമാവധി ലാഭത്തെ പ്രതിനിധീകരിക്കുന്നു.

sa->STATE-A,sb->STATE-B,sc->STATE-C
 sa[i]=max(sa[i-1],sc[i-1]);
 sb[i]=max(sb[i-1],sa[i-1]-prices[i]);
 sc[i]=sb[i-1]+prices[i];

N ആവർത്തനത്തിനുശേഷം, പരമാവധി ലാഭം പരമാവധി ആയിരിക്കും (sa [n-1], sc [n-1]), കാരണം, ലാഭം പരമാവധിയാക്കാൻ ഞങ്ങൾ ആഗ്രഹിക്കുന്നതിനാൽ ഞങ്ങൾ ഒരു സ്റ്റോക്ക് വാങ്ങുകയും വിൽക്കാതിരിക്കുകയും ചെയ്യും.

അടിസ്ഥാന കേസുകൾ:

sa[0]=0;
sb[0]=-prices[0]
sc[0]=INT_MIN

നടപ്പിലാക്കൽ

കൂൾഡ own ൺ ഉപയോഗിച്ച് സ്റ്റോക്ക് വാങ്ങാനും വിൽക്കാനുമുള്ള മികച്ച സമയത്തിനുള്ള സി ++ കോഡ്

#include <bits/stdc++.h> 
using namespace std; 
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        if(n<1)return 0;
       int sa[n],sb[n],sc[n];
        sa[0]=0,sb[0]=-prices[0],sc[0]=INT_MIN;
        for(int i=1;i<n;i++)
        {
            sa[i]=max(sa[i-1],sc[i-1]);
            sb[i]=max(sb[i-1],sa[i-1]-prices[i]);
            sc[i]=sb[i-1]+prices[i];
        }
        return max(sa[n-1],sc[n-1]);  
    }
int main() 
{ 
 vector<int> arr = { 1,2,3,0,2 }; 
 cout<<maxProfit(arr)<<endl; 
 return 0;
}
3

കൂൾഡ own ൺ ഉപയോഗിച്ച് സ്റ്റോക്ക് വാങ്ങാനും വിൽക്കാനുമുള്ള മികച്ച സമയത്തിനുള്ള ജാവ കോഡ്

import java.util.Arrays; 
public class Tutorialcup {
    public static int  maxProfit(int[] prices) {
          int n=prices.length;
    if(n<1)return 0;
    int[] sa = new int[n];
    int[] sb = new int[n];
    int[] sc = new int[n];
    sa[0] = 0;sb[0] = -prices[0]; sc[0] = Integer.MIN_VALUE;

    for (int i = 1; i < n; ++i) {
      sa[i] = Math.max(sa[i-1],sc[i-1]);
      sb[i] = Math.max(sb[i-1],sa[i-1]-prices[i]);
      sc[i] = sb[i-1]+prices[i];
    }

    return Math.max(sa[n-1],sc[n-1]);  
    }
  public static void main(String[] args) {
    int [] arr = {1,2,3,0,2}; 
    int ans=  maxProfit(arr);
    System.out.println(ans);
  }
}
3

കൂൾ‌ഡ own ൺ‌ ലീറ്റ്‌കോഡ് പരിഹാരത്തിനൊപ്പം സ്റ്റോക്ക് വാങ്ങാനും വിൽ‌ക്കാനുമുള്ള മികച്ച സമയത്തിന്റെ സങ്കീർ‌ണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

മുകളിലുള്ള കോഡിന്റെ സമയ സങ്കീർണ്ണതയാണ് O (n) കാരണം ഞങ്ങൾ വില ശ്രേണിയിൽ ഒരു തവണ മാത്രമേ സഞ്ചരിക്കുന്നുള്ളൂ. വില നിരയുടെ ദൈർഘ്യം ഇവിടെ n ആണ്.

സ്ഥല സങ്കീർണ്ണത

മുകളിലുള്ള കോഡിന്റെ സ്ഥല സങ്കീർണ്ണത O (n) കാരണം വിവിധ സംസ്ഥാനങ്ങളുടെ വിവരങ്ങൾ സംഭരിക്കാൻ ഞങ്ങൾ ഒരു അറേ ഉപയോഗിക്കുന്നു.

അവലംബം