Return to Answer

added 1811 characters in body

Source Link

edited Dec 13, 2017 at 12:10

4.7k
15
19

A bit optimized, removing the array posNegs.

class Solution {
    public int maxSubArray(int[] nums)
    {
        final int size = nums.length;

        int max = Integer.MIN_VALUE;

        int firstPosIndex = 0;
        while (firstPosIndex < size && nums[firstPosIndex] <= 0) {
            ++firstPosIndex;
        }
        int lastPosIndex = size; // Exclusive
        while (lastPosIndex > firstPosIndex && nums[lastPosIndex - 1] <= 0) {
            --lastPosIndex;
        }

        // Initial max should there be only negative numbers.
        if (firstPosIndex >= lastPosIndex) {
            for (int i = 0; i < size; ++i) {
                int num = nums[i];
                if (max < num) {
                    max = num;
                }
            }
            return max;
        }

        int sum = 0;
        int i = firstPosIndex;
        while (i < lastPosIndex) {

            // Positive numbers:
            while (i < lastPosIndex && nums[i] > 0) {
                sum += nums[i];
                ++i;
            }
            if (max < sum) {
                max = sum;
            }
            // Negative numbers:
            if (i < lastPosIndex) {
                sum += nums[i];
                ++i;
                while (i < lastPosIndex && nums[i] <= 0) {
                    sum += nums[i];
                    ++i;
                }
                if (sum < 0) {
                    sum = 0;
                }
            }
        }
        return max;
    }
}

A bit optimized, removing the array posNegs.

class Solution {
    public int maxSubArray(int[] nums)
    {
        final int size = nums.length;

        int max = Integer.MIN_VALUE;

        int firstPosIndex = 0;
        while (firstPosIndex < size && nums[firstPosIndex] <= 0) {
            ++firstPosIndex;
        }
        int lastPosIndex = size; // Exclusive
        while (lastPosIndex > firstPosIndex && nums[lastPosIndex - 1] <= 0) {
            --lastPosIndex;
        }

        // Initial max should there be only negative numbers.
        if (firstPosIndex >= lastPosIndex) {
            for (int i = 0; i < size; ++i) {
                int num = nums[i];
                if (max < num) {
                    max = num;
                }
            }
            return max;
        }

        int sum = 0;
        int i = firstPosIndex;
        while (i < lastPosIndex) {

            // Positive numbers:
            while (i < lastPosIndex && nums[i] > 0) {
                sum += nums[i];
                ++i;
            }
            if (max < sum) {
                max = sum;
            }
            // Negative numbers:
            if (i < lastPosIndex) {
                sum += nums[i];
                ++i;
                while (i < lastPosIndex && nums[i] <= 0) {
                    sum += nums[i];
                    ++i;
                }
                if (sum < 0) {
                    sum = 0;
                }
            }
        }
        return max;
    }
}

Source Link

answered Dec 13, 2017 at 10:28

Joop Eggen

4.7k
15
19

Doing the loop several times would be O(n) too, so this version is fine, especially with JS1s adaption. That algorithm needs no further improvement.

However this problem is has some properties that are not exploited.

Negative numbers at front and end can be disregarded.
Ranges of negative only and positive only can be summed.

So:

class Solution {
    public int maxSubArray(int[] nums)
    {
        int size = nums.length;

        // 1. We can discard negative number at front and at end.
        int firstPosIndex = 0;
        while (firstPosIndex < size && nums[firstPosIndex] <= 0) {
            ++firstPosIndex;
        }
        int lastPosIndex = size; // Exclusive
        while (lastPosIndex > firstPosIndex && nums[lastPosIndex - 1] <= 0) {
            --lastPosIndex;
        }

Contrived test data could have 45% negative numbers at both ends of the array.

        // 2. Sum ranges of consecutive positive only or negative only nums.
        int posNegCount = 0;
        boolean rangePositive = true;
        for (int i = firstPosIndex + 1; i < lastPosIndex; ++i) {
            if ((nums[i] > 0) != rangePositive) {
                rangePositive = !rangePositive;
                ++posNegCount;
            }
        }
        posNegCount += posNegCount & 1; // Even, or make 2 arrays.
        int[] posNegs = new int[posNegCount];
        rangePositive = true;
        int posNegIndex = 0;
        for (int i = firstPosIndex + 0; i < lastPosIndex; ++i) {
            int num = nums[i]
            if ((num > 0) != rangePositive) {
                rangePositive = !rangePositive;
                ++posNegIndex;
            }
            posNegs[posNegIndex] += num;
        }

Now a positive range may only contribute to the following positive range, when it supercedes the negative range following.

        int max = 0;
        int sum = 0;
        for (int i = 0; i < posNegCount; ++i) {
            sum += posNeg[i];
            if (sum > max) {
                max = sum;
            }
            ++i;
            if (sum + posNeg[i] > 0) {
                sum += posNeg[i];
            } else {
                sum = 0;
            }
        }
        return max;
    }
}

Not the nicest code, neither very solid. But you asked about a "better" algorithm. Believe it or not, this version could be faster.

It could even be improved.