Опис задачі:

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description/

Вам надано масив prices, де prices[i] — це ціна акцій на i-й день.

Ваша мета — максимізувати прибуток, вибравши один день для купівлі однієї акції та вибравши інший день у майбутньому для продажу цієї акції.

Поверніть максимальний прибуток, який можна отримати від цієї транзакції. Якщо ви не можете отримати жодного прибутку, поверніть 0.

Приклад 1:

Вхід: prices = [7,1,5,3,6,4]  
Вихід: 5  
Пояснення: Купити на 2-й день (ціна = 1) і продати на 5-й день (ціна = 6), прибуток = 6-1 = 5.  
Зверніть увагу, що купити на 2-й день і продати на 1-й день неможливо, бо купівля повинна бути до продажу.

Підхід 1: Брутальна сила

class Solution {  
 /**  
 * Ця функція обчислює максимальний прибуток від купівлі та продажу акції  
 * на основі цін акцій на різні дні, використовуючи підхід брутальної сили.  
 *  
 * @param prices Масив, де prices[i] — це ціна акцій на день i.  
 * @return Максимальний прибуток, який можна отримати. Повертає 0, якщо прибуток неможливий.  
 */  
 public int maxProfit(int[] prices) {  
 int maxProfit = 0; // Змінна для збереження максимального прибутку  

 // Зовнішній цикл: Перебираємо кожен день як потенційний день купівлі  
 for (int i = 0; i < prices.length - 1; i++) {  
 // Внутрішній цикл: Перевіряємо кожен наступний день як потенційний день продажу  
 for (int j = i + 1; j < prices.length; j++) {  
 // Обчислюємо прибуток, віднявши ціну купівлі від ціни продажу  
 int currentProfit = prices[j] - prices[i];  
 // Оновлюємо максимальний прибуток, якщо поточний прибуток більший  
 maxProfit = Math.max(maxProfit, currentProfit);  
 }  
 }  
 return maxProfit; // Повертаємо максимальний знайдений прибуток  
 }  
}

Пояснення:

Мета: Знайти максимальний прибуток, який можна отримати від купівлі та продажу акцій один раз, використовуючи підхід брутальної сили.

Ключові кроки:

• Зовнішній цикл (i): Перебирає кожен день як потенційний день купівлі.
• Внутрішній цикл (j): Для кожного дня купівлі (i), перебирає всі наступні дні, щоб перевірити потенційний день продажу.
• Обчислення прибутку: Прибуток для кожної пари i (день купівлі) і j (день продажу) обчислюється як prices[j] - prices[i].
• Оновлення максимального прибутку: Оновлюється maxProfit, якщо поточний прибуток більший за попередній максимальний.

Приклад виконання:

Вхід:

int[] prices = {7, 1, 5, 3, 6, 4};

Кроки виконання:

Зовнішній цикл (i = 0, ціна купівлі = 7):

• Внутрішній цикл:
• j = 1, ціна продажу = 1 → прибуток = -6 → maxProfit = 0
• j = 2, ціна продажу = 5 → прибуток = -2 → maxProfit = 0
• j = 3, ціна продажу = 3 → прибуток = -4 → maxProfit = 0
• j = 4, ціна продажу = 6 → прибуток = -1 → maxProfit = 0
• j = 5, ціна продажу = 4 → прибуток = -3 → maxProfit = 0

Зовнішній цикл (i = 1, ціна купівлі = 1):

• Внутрішній цикл:
• j = 2, ціна продажу = 5 → прибуток = 4 → maxProfit = 4
• j = 3, ціна продажу = 3 → прибуток = 2 → maxProfit = 4
• j = 4, ціна продажу = 6 → прибуток = 5 → maxProfit = 5
• j = 5, ціна продажу = 4 → прибуток = 3 → maxProfit = 5

Зовнішній цикл (i = 2, ціна купівлі = 5):

• Внутрішній цикл:
• j = 3, ціна продажу = 3 → прибуток = -2 → maxProfit = 5
• j = 4, ціна продажу = 6 → прибуток = 1 → maxProfit = 5
• j = 5, ціна продажу = 4 → прибуток = -1 → maxProfit = 5

Зовнішній цикл (i = 3, ціна купівлі = 3):

• Внутрішній цикл:
• j = 4, ціна продажу = 6 → прибуток = 3 → maxProfit = 5
• j = 5, ціна продажу = 4 → прибуток = 1 → maxProfit = 5

Зовнішній цикл (i = 4, ціна купівлі = 6):

• Внутрішній цикл:
• j = 5, ціна продажу = 4 → прибуток = -2 → maxProfit = 5

Вихід:

5

Часова та Просторова складність:

1. Часова складність: O(n²): Два вкладених цикли перебирають всі пари днів (i, j).
   2.
   Просторова складність: O(1): Використовуються лише кілька змінних (maxProfit, currentProfit), без додаткових виділених пам'яті.

Підхід 2: Рішення за допомогою двох вказівників

class Solution {  
 public int maxProfit(int[] prices) {  

 int left = 0;  
 int right = 1;  
 int maxProfit = 0;  

 while (right < prices.length) {  
 if (prices[left] < prices[right]) { // Якщо прибуток можливий  
 int difference = prices[right] - prices[left];  
 maxProfit = Math.max(maxProfit, difference);  
 } else { // Якщо поточна ціна нижча за ціну купівлі  
 left = right; // Переміщаємо день купівлі на поточний день  
 }  
 right += 1; // Завжди переміщаємо день продажу вперед  
 }  
 }  
}

Пояснення:

Мета:

• Знайти максимальний прибуток, який можна отримати від купівлі та продажу акцій один раз.
• Забезпечити, щоб не відбулося жодної транзакції, якщо прибуток неможливий.

Приклад введення:

int[] prices = {7, 1, 5, 3, 6, 4};

Кроки виконання:

Ініціалізація:

• left = 0 (день купівлі).
• right = 1 (день продажу).
• maxProfit = 0.

Ітерація 1 (left = 0, right = 1):

• Порівнюємо prices[left] = 7 і prices[right] = 1.
• prices[left] >= prices[right], тому переміщаємо left = right = 1.
• Інкрементуємо right = 2.

Ітерація 2 (left = 1, right = 2):

• Порівнюємо prices[left] = 1 і prices[right] = 5.
• prices[left] < prices[right], тому обчислюємо прибуток:
• difference = prices[right] - prices[left] = 5 - 1 = 4.
• maxProfit = Math.max(0, 4) = 4.
• Інкрементуємо right = 3.

Ітерація 3 (left = 1, right = 3):

• Порівнюємо prices[left] = 1 і prices[right] = 3.
• prices[left] < prices[right], тому обчислюємо прибуток:
• difference = prices[right] - prices[left] = 3 - 1 = 2.
• maxProfit = Math.max(4, 2) = 4.
• Інкрементуємо right = 4.

Ітерація 4 (left = 1, right = 4):

• Порівнюємо prices[left] = 1 і prices[right] = 6.
• prices[left] < prices[right], тому обчислюємо прибуток:
• difference = prices[right] - prices[left] = 6 - 1 = 5.
• maxProfit = Math.max(4, 5) = 5.
• Інкрементуємо right = 5.

Ітерація 5 (left = 1, right = 5):

• Порівнюємо prices[left] = 1 і prices[right] = 4.
• prices[left] < prices[right], тому обчислюємо прибуток:
• difference = prices[right] - prices[left] = 4 - 1 = 3.
• maxProfit = Math.max(5, 3) = 5.
• Інкрементуємо right = 6.

Вихід з циклу:

• Цикл завершується, оскільки right стає рівним prices.length.

Кінцевий результат:

maxProfit = 5

Найкраща транзакція — купити на 1-й день (ціна = 1) і продати на 4-й день (ціна = 6), отримавши прибуток 6 - 1 = 5.

Часова та Просторова складність:

1. Часова складність: O(n)

• Кожна ціна перевіряється один раз, оскільки right інкрементується через масив, а left коригується, коли це необхідно.

1. Просторова складність: O(1)

• Використовуються лише кілька змінних для обчислень без додаткових структур даних.

Що ви думаєте про цю статтю? Чи є у вас власне рішення, яке вам ставили на інтерв'ю? Давайте обговоримо в коментарях!

Якщо вам сподобалася ця стаття, поставте 👏 і поділіться нею з тими, хто може отримати користь. Натискайте «підписатися», щоб не пропустити оновлення. Побачимося в наступній статті.😃

Також можете перевірити інші статті нижче.

[

Leetcode — Valid Anagram (Java)

Зміст:

medium.com

](/@jayrammanale/leetcode-valid-anagram-java-98bfa3566b15?source=postpage-----84ada01fba4b--------------------------------)

[

Leetcode — Two Sum (Java)

Виклик "Two Sum": Стратегії для підвищення навичок алгоритмів

medium.com

](/@jayrammanale/leetcode-two-sum-java-ce5fd61fcf85?source=postpage-----84ada01fba4b--------------------------------)

[

🚀 Відкрийте ексклюзивні технічні інсайти — підпишіться зараз!

🚀 Відкрийте ексклюзивні технічні інсайти — підпишіться зараз! 💻 Любите програмування, туториали та поради експертів? 🚀 Підпишіться, щоб отримувати: …

medium.com

](/@jayrammanale/subscribe?source=postpage-----84ada01fba4b--------------------------------)

Перекладено з: Leetcode — Best Time to Buy and Sell Stock