Для некоторого контекста это проблема LeetCode # 122: лучшее время для покупки и продажи акций II. В основном, предоставляется массив целых чисел, представляющих цену акции в день i, где 0 <= i <array.size (), и нам нужно рассчитать максимальную прибыль, которая будет получена. Если это проблема, которую вы хотели бы сначала попробовать для себя, пожалуйста, не обращайте внимания на вопрос. </p>
Но для всех, кто может ответить, я пытаюсь обернуть голову, как это решение грубой силы дает O (п ^ п) сложность времени. Я ни в чем не сомневаюсь, я просто хочу понять, как это работает. В частности, я смотрю на рекурсию внутри вложенных циклов for и на то, как мы вычисляем, как часто она вызывается. Также было бы хорошо понять, как это относится к грубой силе (что означает проверка каждого возможного набора транзакций?)
public int calculate(int prices[], int s) {
if (s >= prices.length)
return 0;
int max = 0;
for (int start = s; start < prices.length; start++) {
int maxprofit = 0;
for (int i = start + 1; i < prices.length; i++) {
if (prices[start] < prices[i]) {
int profit = calculate(prices, i + 1) + prices[i] - prices[start];
if (profit > maxprofit)
maxprofit = profit;
}
}
if (maxprofit > max)
max = maxprofit;
}
return max;
}