ყიდვისა და გაყიდვის საუკეთესო დრო II Leetcode Solution


Რთული ტური Easy
ხშირად ეკითხებიან Amazon დე შოუ Facebook microsoft Morgan Stanley Uber
Array ხარბ

პრობლემის განცხადება

პრობლემში ”საუკეთესო დრო ყიდვისა და გაყიდვის საფონდო II”, მოცემულია მასივი, სადაც მასივის თითოეული ელემენტი შეიცავს მოცემული აქციის ფასს ამ დღეს.

განმარტება გარიგების ყიდულობს ერთ აქციას და ყიდის ამ ერთ წილს.

ჩვენი ამოცანაა მაქსიმალური მოგების პოვნა შემდეგი შეზღუდვებით:

  1. ჩვენ არ შეგვიძლია ახალი აქციების ყიდვა, თუ წინა აქციები არ გავყიდეთ. ამ დროს ჩვენ შეგვიძლია მაქსიმუმ ერთი მარაგი გვქონდეს.
  2. ჩვენ შეგვიძლია გავაკეთოთ იმდენი ოპერაცია, რამდენიც გვსურს.

მაგალითი

prices = [7,1,5,3,6,4]
7

განმარტება: მაქსიმალური მოგება, რომლის მიღებაც არის 7. ქვემოთ მოცემულია გარიგების დეტალები:

პირველი დღე: დაისვენე

მეორე დღე: ყიდვა

მესამე დღე: გაყიდვა

მეოთხე დღე: ყიდვა

მეხუთე დღე: გაყიდვა

მეექვსე დღე: დასვენება

მიდგომა საუკეთესო დროის ყიდვისა და გაყიდვის საფონდო II Leetcode Solution- ისთვის

ვინაიდან გარიგებების რაოდენობის შეზღუდვა არ გვაქვს, ამიტომ მოვიფიქრებთ ა ხარბი ალგორითმი აქ. ასე რომ, ყოველ ჯერზე ჩვენ შეიძენთ აქციას მინიმალურ ფასად და გავყიდით მას მაქსიმალურ ფასად. შეგვიძლია შევაჯამოთ ის, რომ თითოეულ მინიმებზე ვიყიდით საფონდო აქციას და თითოეულ მაქსიმუმზე გავყიდით აქციებს. ეს აიხსნება ქვემოთ მოცემულ ფიგურაში. ეს არის ნაკვეთი აქციის ფასსა და დღეებს შორის. leetcode- ის გადაწყვეტილება II. ყიდვისა და გაყიდვის საუკეთესო დროისთვის

ამის გაკეთება უფრო მარტივია, თუ დავაკვირდებით, რომ მაქსიმუმი იქმნება, როდესაც მინიმებს მცირე მნიშვნელობები ემატება. ამრიგად, მაქსიმალური მოგების გამოსათვლელად ყველა მინიმუმსა და მაქსიმალზე თვალყურისდევნების შემთხვევაში, ჩვენ შეგვიძლია პირდაპირ დავამატოთ ის მნიშვნელობები ჩვენს მოგებას, რომლისთვისაც დავადგინეთ პოზიტიური დახრა, რაც არის ფასები [i]> ფასები [i-1]. ყველა ასეთი მნიშვნელობის დამატება მოგვცემს მაქსიმალურ მოგებას.

leetcode- ის გადაწყვეტილება II. ყიდვისა და გაყიდვის საუკეთესო დროისთვის

განხორციელება

C ++ კოდი საუკეთესო დროის ყიდვისა და გაყიდვის საფონდო II

#include <bits/stdc++.h> 
using namespace std; 
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        int ans = 0;
        for (int i = 1; i < n; i++) {
            if (prices[i] > prices[i - 1])
                ans += prices[i] - prices[i - 1];
        }
        return ans;
    }
int main() 
{ 
 vector<int> arr = { 7,1,5,3,6,4 }; 
 cout<<maxProfit(arr)<<endl; 
 return 0;
}
7

ჯავის კოდი საუკეთესო დროის ყიდვა-გაყიდვისთვის II

import java.util.Arrays; 
public class Tutorialcup {
     public static int maxProfit(int[] prices) {
        int ans = 0;
        int n=prices.length;
        for (int i = 1; i < n; i++) {
            if (prices[i] > prices[i - 1])
                ans += prices[i] - prices[i - 1];
        }
        return ans;
    }
  public static void main(String[] args) {
    int [] arr = {7,1,5,3,6,4}; 
    int ans=  maxProfit(arr);
    System.out.println(ans);
  }
}
7

სირთულის ანალიზი საუკეთესო დროის ყიდვისა და გაყიდვის საფონდო II Leetcode Solution

დროის სირთულე

ზემოთ მოცემული კოდის სირთულეა O (n) რადგან ფასის მასივს მხოლოდ ერთხელ ვათვალიერებთ. აქ n არის ფასების მასივის სიგრძე.

კოსმოსური სირთულის

ზემოთ მოცემული კოდის სივრცის სირთულეა O (1) რადგან მეხსიერებას მხოლოდ პასუხის შესანახად ვიყენებთ.

ლიტერატურა