我正在尝试设计一个O(nlogn)时间的分治算法来解决以下现实问题 -
假设我们有一组股票价格的数组。提供一个算法,输出一个包含每个i天最大利润的数组。
例如,如果我们有数组A=[4,6,2,1],则我们的天数表示每个索引,我们的输出将是一个值为[2,-4,-1,-1]的数组,其中最后一天的值为-A[i]。
我已经设计出了一个暴力算法-
此外,我不确定上述算法的时间复杂度是O(n)还是O(n^2)。在该算法中,最大的花费在于查找最大值,其他所有操作都是O(1)。
有人能帮忙解答吗?谢谢!
假设我们有一组股票价格的数组。提供一个算法,输出一个包含每个i天最大利润的数组。
例如,如果我们有数组A=[4,6,2,1],则我们的天数表示每个索引,我们的输出将是一个值为[2,-4,-1,-1]的数组,其中最后一天的值为-A[i]。
我已经设计出了一个暴力算法-
1.) Scans the array for max after A[i]
2.) Subtracts A[i] with max, places value in A', iterates to next day
3.) When max reaches itself, repeat steps 1 & 2
4.) When you reach the end, the value is -A[i], return
此外,我不确定上述算法的时间复杂度是O(n)还是O(n^2)。在该算法中,最大的花费在于查找最大值,其他所有操作都是O(1)。
有人能帮忙解答吗?谢谢!