Когда покупать/продавать акции? Дан массив, содержащий дневную цену акции. Старайтесь найти максимальную прибыль.

Input: [20,10,30,44,26,40,50]
Output: 58
Explanation: 
Buy on day 2 and sell on day 4, profit = 44-10 = 34.
Buy on day 5 and sell on day 7, profit = 50-26 = 24.

Мыслительный процесс:

Из предыдущего вопроса Переместить нули мы знаем, что, по крайней мере, мы хотим пройти по входному массиву один раз, поэтому временная сложность будет равна O(n). Мы можем использовать дополнительную структуру данных (например, Array/Linked List/Map/Set), чтобы хранить ежедневную прибыль и суммировать прибыль в конце. Но подождите секунду, разве нас действительно волнует, в какой день мы заработаем, сколько прибыли? Или мы можем просто суммировать общую прибыль, перебирая входной массив?

Решение:

makeProfit(prices) {
    // Use a constant space O(1) to record total profit.
    let profit = 0;
    // While looping through the input array, we calculate the profit and add it to the sum.
    for(let i = 0; i < prices.length - 1; i++) {
        profit += Math.max(0, prices[i + 1] - prices[i]);
    }
    return profit;
};

Ключевые примечания:

  1. Экономьте место
  2. Как отследить и рассчитать прибыль от входного массива?

Какой следующий вопрос?

Найти дубликаты — Учитывая массив чисел, вернуть true, если какое-либо число встречается в массиве более одного раза, в противном случае вернуть false. (мысленный процесс и решение)

Перед тем, как ты уйдешь -

Нет лучшего способа поддержать меня, чем подписаться на Medium (Victor Lin). Дайте мне знать, что я должен писать больше!

Знаете ли вы, что вы можете дать до 50 👏, нажав на кнопку 👏? Попробуйте, если вам очень понравилась эта статья!