从股票买卖到游戏得分：用Kadane算法解决你身边的实际问题（Python/Java实现）

1. 当算法遇见生活：从股票收益说起

想象你是一位股票投资者，过去一周的每日收益记录如下（单位：万元）：

daily_profit = [3, -2, 5, -1, 6, -4, 2]

如果只关注单日收益，最大值显然是第5天的6万元。但真正聪明的投资者会思考：**连续持有股票的最大潜在收益是多少？**这正是Kadane算法要解决的经典问题——最大子数组和。

传统暴力解法需要检查所有可能的连续区间，时间复杂度高达O(n²)。而Kadane算法通过动态规划思想，只需一次遍历（O(n)）就能找到答案。就像股票投资中，我们不需要尝试所有买卖组合，只需在每天决策时考虑：

1. 继续持有前几天的仓位
2. 从今天重新建仓

关键变量 ：

• current_max ：当前连续持仓的累计收益
• global_max ：历史最佳连续收益

// Java实现
public int maxSubArray(int[] nums) {
    int currentMax = nums[0];
    int globalMax = nums[0];
    for (int i = 1; i < nums.length; i++) {
        currentMax = Math.max(nums[i], currentMax + nums[i]);
        globalMax = Math.max(globalMax, currentMax);
    }
    return globalMax;
}

应用到我们的股票数据：

• 第3天时， current_max 从1（3-2）变为5（放弃前两天）
• 第5天达到峰值：3-2+5-1+6=11万元

2. 游戏玩家的得分策略

现在换个场景：你正在玩一款闯关游戏，每关得分记录如下：

关卡得分: [2, -3, 5, -1, 3, -2, 4]

游戏规则允许选择连续关卡组合参赛，如何选择能获得最高总评分？这正是最大子数组和的另一个应用场景。

暴力解法缺陷 ：

• 检查所有可能的起始和结束关卡
• 7关需要检查28种组合（7×8/2）
• 关卡数增加到100时，组合数达5050种

Kadane算法优化 ：

def max_subarray(arr):
    current_max = global_max = arr[0]
    for num in arr[1:]:
        current_max = max(num, current_max + num)
        global_max = max(global_max, current_max)
    return global_max

应用到游戏得分：

• 最佳连续关卡：第3关到第7关（5-1+3-2+4=9分）
• 即使中间有扣分关卡，整体仍是最优选择

3. 算法核心：动态规划的智慧

Kadane算法的精妙之处在于其动态规划思想。与常规动态规划不同，它通过两个变量就实现了状态转移：

变量	作用	更新规则
current_max	记录以当前元素结尾的最大和	max(当前元素, current_max + 当前元素)
global_max	记录全局最大值	max(global_max, current_max)

为什么有效？

1. 最优子结构 ：全局最优解包含局部最优解
2. 无后效性 ：当前决策只依赖前一状态
3. 状态压缩 ：只需保存前一个状态，无需完整DP表

提示：当数组全为负数时，算法会正确返回最大的单个元素值

4. 实战扩展：环形数组处理

考虑更复杂的情况——环形数组。比如记录连续24小时的店铺盈亏：

hourly_profit = [8, -1, -1, -1, 8, -1, -1]

如果数组首尾相连，最大子数组可能是跨越 midnight 的组合。解决方法：

1. 计算常规最大子数组和（不跨越首尾）
2. 计算数组总和减去最小子数组和（跨越首尾的情况）
3. 取两者较大值

public int maxSubarraySumCircular(int[] nums) {
    int total = 0, maxSum = nums[0], minSum = nums[0];
    int currentMax = 0, currentMin = 0;
    for (int num : nums) {
        currentMax = Math.max(num, currentMax + num);
        maxSum = Math.max(maxSum, currentMax);
        currentMin = Math.min(num, currentMin + num);
        minSum = Math.min(minSum, currentMin);
        total += num;
    }
    return maxSum > 0 ? Math.max(maxSum, total - minSum) : maxSum;
}

5. 更多应用场景

Kadane算法的变体可以解决各类连续序列优化问题：

1. 基因组分析 ：寻找DNA序列中GC含量最高的连续片段
2. 商业决策 ：确定连续多日促销的最佳时段
3. 传感器数据 ：检测连续时间窗口内的最大信号强度

性能对比 ：

数据规模	暴力解法耗时	Kadane算法耗时
100	~5ms	~0.01ms
10,000	~500ms	~1ms
1,000,000	超时	~100ms

实际项目中，我曾用该算法优化电商促销时段选择，将计算时间从分钟级降到毫秒级。特别是在处理用户行为流水数据时，这种高效算法能实时给出最优解。