הזמן הטוב ביותר לרכוש ולמכור פתרון מניות Leetcode II


רמת קושי קַל
נשאל לעתים קרובות אמזון בעברית דה שו פייסבוק מיקרוסופט מורגן סטנלי סופר
מערך חמדן

הצהרת בעיה

בבעיה "הזמן הטוב ביותר לקנות ולמכור מניות II", אנו מקבלים מערך שבו כל אלמנט במערך מכיל את מחיר המניה הנתונה באותו יום.

ההגדרה של עסקה קונה מניה אחת במניה ומכירת אותה מניה אחת.

המשימה שלנו היא למצוא את הרווח המרבי תחת המגבלות הבאות:

  1. איננו יכולים לקנות מניה חדשה אם לא מכרנו את המניה הקודמת. כלומר, בכל פעם שנוכל להחזיק לכל היותר מניה אחת.
  2. אנחנו יכולים לעשות כמה עסקאות שאנחנו רוצים.

דוגמה

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

הסבר: הרווח המקסימלי שניתן להשיג הוא 7. להלן פירוט העסקה:

יום ראשון: מנוחה

יום שני: לקנות

יום שלישי: למכור

היום הרביעי: לקנות

היום החמישי: למכור

היום השישי: מנוחה

הגישה לזמן הטוב ביותר לרכישה ומכירה של פתרון Leetcode מניות II

מכיוון שאין לנו מגבלות על מספר העסקאות, אז נחשוב על אלגוריתם חמדן פה. אז בכל פעם נקנה מניה במחיר מינימום ונמכור אותה במחיר מקסימלי. אנו יכולים לסכם זאת כשבכל מינימום נקנה מניה ובכל מקסימום נמכור מניה. זה מוסבר באיור הבא. זוהי עלילה בין מחיר המניה לימים. פתרון 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

קוד Java לזמן הטוב ביותר לקנייה ומכירה של מלאי 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

ניתוח מורכבות הזמן הטוב ביותר לרכישה ומכירה של פתרון Leetcode מניות II

מורכבות זמן

מורכבות הזמן של הקוד הנ"ל היא O (n) כי אנחנו חוצים את מערך המחירים רק פעם אחת. כאן n הוא אורך מערך המחירים.

מורכבות חלל

מורכבות החלל של הקוד הנ"ל היא O (1) כי אנו משתמשים בזיכרון רק כדי לאחסן את התשובה.

הפניות