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

1. 解题思路： 由于已经使用动态规划解决了连续子数组的最大和（一）,那么思路相同，只不过这次的输出是要求输出这个连续子数组，那么可以添加一个变量，用于记录返回数组的末尾元素位置，同时还需要一个变量记录一下连续的数组长度。

2. 遇到的坑：

   2.1 由于遇到多个最优解的字符串 返回最长的那个 这里的最长子数组有两种可能，一种是dp[i-1]=0，那么之后的序列可以包含dp[i-1]也可以从dp[i]开始，比如：1 2 -3 4 -1 1 -3 2，对应的dp数组为 1 3 0 4 3 4 1 3，可以看到最大值为4，并且有两个，最大数组分别是：[1,2,-3,4]或者是[4]，那么怎么解决这个问题呢？这个问题的解决位于第25行 dp数组的构建时，当遇到dp[i-1]=0时仍然使得长度length++即可。第二种可能：1 2 3 -8 3 3的情况 有[1,2,3]和[3,3]，这个问题的解决方式是在第34行，当比较最大dp值的时候，当dp相同，比较一下长度是否也变大了。

   2.2 小细节：由于时间复杂度O(n),空间复杂度是O(1)，在求连续子数组最大和（一）的基础上优化，由于dp数组并不是都需要用到，我只需要使用最大值来更新记录遍历的一个dp即可。空间复杂度为O(1)

 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param array int整型一维数组 
 * @param arrayLen int array数组长度
 * @return int整型一维数组
 * @return int* returnSize 返回数组行数
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
int* FindGreatestSumOfSubArray(int* array, int arrayLen, int* returnSize ) {
    // 先写一个计算连续子数组最大和的dp解 只需要记录一下每个位置包含的元素个数 
    if(array==NULL||arrayLen==0)
        return NULL;
    if(arrayLen==1){
        *returnSize=1;
        return array;
    }
    int dphere=array[0];
    int maxnum=array[0];
    int loc=0;//记录最大值位置
    int length=1;//记录连续数组的长度
    int num_length=0;
    for(int i=1;i<arrayLen;i++){
        if(dphere+array[i]>=array[i]){
            length++;
            dphere=dphere+array[i];
        }
        else{
            length=1;
            dphere=array[i];
        }
        //如果最大值更新了 同时更新当前最大值的位置 以及子数组的长度
        if(maxnum<=dphere||(maxnum==dphere&&length>num_length)){
            loc=i;
            num_length=length;
            maxnum=dphere;
        }
       
    }
    *returnSize=num_length;
    return &array[loc-num_length+1];
}