"What is the fastest solution for finding the maximum sum of a subarray?"

Question

Question

Given an array, find the longest continuous sub-array which has maximum sum.

My Approach

First, I solved this problem using dynamic programming which effectively solved the problem in \$O(n)\$ time as opposed to the brute force approach. For each iteration, I checked if the sum is less than 0, and if true, I ran a new sum whenever the sum became less than 0.

Also, I kept track of the current maximum in each iteration.

class Solution
{
    public int maxSubArray(int[] nums)
    {    
        /*
         * get the array size.
         */
        int size = nums.length;

        /*
         * initialize the variables to the first index of the array.
         */
        int sum = nums[0];
        int max = nums[0];

        /*
         * iterate using a loop from 1 to n-1.
         * set sum to 0 if current is less than 0.
         * for negative results, no need to add sum as the largest sum is the smallest negative number itself.
         * update max if sum is greater.
         */
        for (int i = 1; i < size; i++)
        {
            if (sum < 0)
                sum = 0;

            sum += nums[i];
            if (sum > max)
                max = sum;
        }
        return max;
    }
}

As you can see from the above, I have kept the code as compact as possible. I also stored the array length also in a variable for faster execution. And the solution is linear time.

Issues

• When I submit on LeetCode, I am told that my code is only 17% faster as compared to the rest of Java submissions for the same problem.
• How do I make this code more optimised (or rather, is there any way to optimise this code even more?)
• Is there a better/different approach to this problem?
• I haven't used any Java APIs, library functions etc. then could anyone please tell me where is the time being consumed (or rather, which is the most costly operation in my algorithm and is there any way to reduce the costly operation?)

Notes

• The solution is correct as it passed all 200 test cases! (It's just that it is slow).

  • To find the required sub-array, I need to iterate over the array at least once just to see if my sum can be maximised. In such a case, the minimum time has to be linear time and if this observation were true, then all the other faster solutions must run at least linear time. Again, if the above were true, then it means the faster solutions are using techniques to make the execution faster despite it being linear time, right?

Answer 1

Can't get much better

First of all, I would have to agree with the commenters that your solution is fine. Any further gains upon your solution would probably depend on random factors in the Leetcode judging system. Your main loop does the minimal amount of work necessary to solve the problem.

Reduce code?

That being said, I went ahead and tried a few things to see how random the Leetcode judging system was. I ended up with this code which is essentially the same as the original code except it doesn't special case the first array entry and is therefore a little smaller:

class Solution {
    public int maxSubArray(int[] nums)
    {
        int size = nums.length;
        int sum = 0;
        int max = Integer.MIN_VALUE;

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

I submitted this code several times and randomly got a submission in the 98.67% percentile (13 ms). I also had submissions that scored 85% (14 ms), 56% (15 ms), 32% (16 ms), and 18% (17 ms). Given the fact that the same code varied in time between 13 ms and 17 ms, I would say that random factors have more to do with your score than the actual code.

You can see my 13 ms submission here. I'm not sure if that link is private to my account or not, but you could always just copy and paste my code and submit many times yourself.

Answer 2

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.

---

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;
    }
}