卡丹尔算法(max_subarray_problem)

问题介绍

假设我们有一个数组，其中第i个元素代表某支股票在第i天的价格。若仅允许完成一次交易（即买入一股并卖出一股），则设计一个算法以求得最大利润。从抽象层面来看，问题转化为寻找一个子数组nums[i, j] (0 <= i < j <= n)，使得nums[j] - nums[i]的差值达到最大。显然，可以采用暴力解法，其时间复杂度为O(n*n)。然而，还存在一种更为高效的解决方案，能够将时间复杂度降至O(n)，这便是广为人知的卡丹尔算法。该算法的核心思想源于动态规划理念，只需维护一个dp数组来记录以当前位置i结尾的最大子数组和。由于必须包含位置i的元素，因此递推关系式可表示为：dp[i] = dp[i - 1] + nums[i] - nums[i - 1]。根据题意要求，dp[i]的最小值应为0，因此最终表达式为：dp[i] = max(0, dp[i - 1] + nums[i] - nums[i - 1])。遍历整个dp数组后即可得到最大值。此外，在扫描nums数组时还可以进一步优化空间复杂度：用变量max_ending_here表示当前的dp[i]值，并用另一个变量max_so_far来保存所有出现过的最大值。这样可以将空间复杂度由原来的O(n)降低至O(1)

求解

    #includ