Ambiguity for negative numbers.


  • 0
    L

    This is a well-known problem, for example, Jon Bentley has quite a good treatment in his book `Programming Perls'. But the answer, as well as the solution details, depends on what the 'maximum sum' is defined for negative numbers.

    For example [-1, -3, -2]. A natural approach is to consider the sum of empty array as zero, sum([]) = 0. Because empty array [] is sub array of all arrays.

    The concise solution based on this assumption is as the following:

    int maxsum(int* xs, int n) {
        int i, m, sum;
        for (i = m = sum = 0; i < n; ++i) {
            sum = max(sum + xs[i], 0);
            m = max(m, sum);
        }
        return m;
    }
    

    Where max can be defined either as macro or function like:

    int max(int a, int b) { return a < b ? b : a; }
    

    However, the OJ system does NOT treat empty array as valid sub-array. It forces the sub-array contains at least one element, Thus we need adjust the above solution a bit:

    int ojpass(int* xs, int n) {
        int i, m, sum;
        for (m = sum = xs[0], i = 1; i < n; ++i) {
            sum = max(sum + xs[i], xs[i]);
            m = max(m, sum);
        }
        return m;
    }

  • 0
    L

    Just for fun: 1 line Python solver:

    return reduce(lambda m, n: [max(m[0], max(m[1]+n, n)), max(m[1]+n, n)], nums[1:], [nums[0], nums[0]])[0]
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.