为何最大子数组的和的函数不能正确处理全部是负数的情况？

Question

有下面的函数，返回一个整数数组中 “最大子数组的和” ，max2 为何返回不对呢？

 

//返回一个数组中最大的子数组的和。 

# include <iostream>
# include <stdio.h>
# include <string.h>


int MaxSum(int* arr, int size)
{
    int current = 0;   //current max sum
    int max = current; 

    for (int i = 0; i < size; i++)
    {
        if (current < 0)
            current = 0; 
        current += arr[i]; 
        if (current > max)
            max = current; 
    }
    return max; 
}

int main(void)
{
    char x[40], y[40];

    int a1[5] = { -1, 5, 6, -7, 3 }; 
    int a2[5] = { -5, -4, -8, -1, -10 }; 
    int a3[5] = { -1, 5, 6, -7, 10 }; 

    int max1, max2, max3; 
    max1 = MaxSum(a1, 5); 
    max2 = MaxSum(a2, 5); //这个应该返回 -1， 但是返回 0. 
    max3 = MaxSum(a3, 5);
}

Answer 1

if (current < 0)current = 0;

if (current > max)max = current;

a2最大子数组和是负数，都比0小，那最终max就是等于0

Answer 2

@bekote  

int current = 0; //current max sum

改为第一个数组元素，是不是就对了？

int current = arr[0]; //current max sum

Answer 3

if (current < 0)current = 0;有这句你改成第一个数组元素，结果也还是0

Answer 4

这个好像要用贪心解，用一个数组，存当前每个位置的最大数组和

 

Answer 5

最大子数组的和即使是负数， 也是正常的啊。  没有规定说数值的和必须大于 0 .