Something wrong with 4.1-5

[wubugui]

这个算法有一点问题

FIND-MAXIMUM-SUBARRAY(A, low, high)
    max = A[low]
  j-max = A[low]
  left = right = low
  j-left = j-right = low

    for j = low + 1 to high
    sum = j-max + A[j]

    if sum > j-max
      j-max = sum
      j-right = j
    else 
      j-max = 0
      j-left = j + 1

    if j-max > max
      max = j-max
      left = j-left
      right = j-right

  return(left, right, max)

如果遇到负数就抛弃前面所有的和，遇到类似这样的序列{0,13,-1,2}就会出问题。
所以应该是前面所有的和加起来小于零了才抛弃，有最大值就更新最大值。
这个算法应该是对的：

    struct Ret_C4
    {
        int low, high;
        float sum;
        Ret_C4(int clow,int chigh,float csum) : low(clow), high(chigh), sum(csum){}
    };
    Ret_C4 find_max_subarray_iter_n(float *A, int low, int high)
    {
        float sum = 0;
        Ret_C4 ret(low,low,0);
        int cur_begin = low;
        int cur_end = low;
        for (size_t i = low; i <= high; i++)
        {
            sum += A[i];
            cur_end = i;
            if (sum<0)
            {
                sum = 0;
                cur_begin = i + 1;
                continue;
            }

            if (sum > ret.sum)
            {
                ret.sum = sum;
                ret.high = cur_end;
                ret.low = cur_begin;
            }
        }
        return ret;
    }

[HardySimpson]

哈哈，被你发现了，的确，那天后来我就发现我这个解法是错误的，碰到一个负数就嗝屁了。后来还没来得及更新。