1 /* 2 * 动态规划实现，算法复杂度O(n) 3 */ 4 int maxSubSequenceSum3(int a[], int len) 5 { 6     int i; 7     int curSum; /* 当前序列和 */ 8     int maxSum; /* 最大序列和 */ 9 10     /* 初始化当前序列和为0 */11     curSum = 0;12 13     /* 初始化最大子序列和为序列第一个元素 */14     maxSum = a[0];15 16     /* 开始循环求子序列和 */17     for (i = 0; i < len; i++)18     {19         curSum = curSum + a[i];20 21         /* 与最大子序列和比较，更新最大子序列和 */22         if (curSum > maxSum)23   {24             maxSum = curSum;25         }26 27         /* 动态规划部分，舍弃当前和为负的子序列 */28         if (curSum < 0)29         {30             curSum = 0;31         }32     }33     return maxSum;34 }