最大子段和问题在C语言中有多种解法，以下是主要方法及实现：

一、动态规划法（Kadane算法）

这是最优解法，时间复杂度为O（n）。

1. 核心思想 ：维护当前子段和cursum，若cursum为负则重置为0，否则累加当前元素。同时记录最大子段和maxsum。

2. 实现代码 ：

   #include <stdio.h>
   int maxSubSum(int *a, int n) {
       int cursum = a, maxsum = a;
       for (int i = 1; i < n; i++) {
           cursum = (cursum > 0) ? cursum + a[i] : a[i];
           if (cursum > maxsum) maxsum = cursum;
       }
       return maxsum;
   }
   

二、分治法

将数组分为左右两部分，分别求最大子段和，再考虑跨越中点的子段和。

1. 核心步骤 ：

   • 递归求解左半部分最大子段和leftSum；

   • 递归求解右半部分最大子段和rightSum；

   • 求解跨越中点的最大子段和crossSum（从中间向左累加最大值，再向右累加最大值）；

   • 返回三者中的最大值。

三、蛮力法

枚举所有子段，计算其和并比较，时间复杂度为O（n³）。

1. 实现思路 ：三重循环遍历所有可能的子段起始和结束位置，计算子段和并更新最大值。

四、其他优化方法

• 初始化优化 ：若全为负数，可设置maxsum为0（根据题目要求）；

• 边界条件处理 ：当cursum降为0时重置，避免无效累加。

总结

动态规划法（Kadane算法）是解决最大子段和问题的最优解法，分治法和蛮力法适用于教学或对比分析。实际应用中优先选择动态规划法。