C语言求解连续子数组的最大和

1. 解题思路：动态规划（dp）问题，对于一个连续的数组：1 -2 3 10 -4 7 2 -5，当计算第i个dp时，此时需要根据dp[i-1]来推算出dp[i]的值，此时dp[i]相比于dp[i-1]的变数 只有a[i]这个值，接下来应该判断a[i]是否有可能添加到dp[i-1]的序列中呢？如果说添加了这个a[i]比dp[i-1]+a[i]>a[i]，那么dp[i]是应该包含a[i]的，否则dp[i-1]+a[i]<a[i] 那个dp[i]=a[i];

2. 当遍历到第i个元素时，判断在它前面的连续子序列和是否大于0，如果大于0，则以位置i结尾的最大连续子序列和为元素i和前面的连续子序列和相加；否则，则以位置i结尾的最大连续子序列和为元素i。

3. 怎么理解动态规划数组dp[i]呢？根据2可以知道 dp[i]理解为以元素i结尾的连续子序列和 由于是连续的子数组 因此计算dp[i]必须包含dp[i-1]

 * 
 * @param array int整型一维数组 
 * @param arrayLen int array数组长度
 * @return int整型
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
int FindGreatestSumOfSubArray(int* array, int arrayLen ) {
   //动态规划问题 先考虑dp dp[i]=dp[i-1]+a[i],(dp[i-1]+a[i]>a[i]) or dp[i]=a[i],(dp[i-1]+a[i]<a[i])
    //dp[0]=a[0] 也就是已知前i-1个数组和的最大值 如果判断第i个 那么需要判断是继续包含这个数字 还是从子个数字开始新的序列
    if(array==NULL||arrayLen==0)
        return 0;
    int *dp=(int *)malloc(sizeof(int)*arrayLen);
    dp[0]=array[0];
    for(int i=1;i<arrayLen;i++)
    {
        if (dp[i-1]+array[i]>array[i])
            dp[i]=dp[i-1]+array[i];
        else
            dp[i]=array[i];
    }
    int maxnum=dp[0];
    for(int i=1;i<arrayLen;i++){
        if(dp[i]>maxnum)
            maxnum=dp[i];
    }
    return maxnum;
}