2
\$\begingroup\$

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?
\$\endgroup\$
  • \$\begingroup\$ 1. This IS dynamic programming as it goes through all the possible approaches and saves time by keeping a track of already computed sub-problems. This is in NO WAY greedy as a greedy algorithm need not go over all possible values and doesn't have anything to do with reducing the sub-problems size. \$\endgroup\$ – enigma6174 Dec 12 '17 at 21:29
  • \$\begingroup\$ 2. Like I said, my code is ONLY 17% faster, which puts me at the bottom of the leaderboard and I really would like to know how the toppers are getting it done, their approach etc. Finally, that is the whole point of this forum isn't it? Get my code reviewed by better coders and gain valuable insight \$\endgroup\$ – enigma6174 Dec 12 '17 at 21:31
  • 1
    \$\begingroup\$ What are the topmost leader getting? Have you tried using a foreach style loop instead? \$\endgroup\$ – Austin Hastings Dec 12 '17 at 22:12
  • 1
    \$\begingroup\$ Note: LeetCode measures precision by milliseconds, which is not that detailed. Submitting the code multiple times may give different results. I've took a variation of this code (removed everything unrelated to creating the array) and my code is sometimes faster than 34%, sometimes faster than 55% of other Java submissions. I'm sure it can be 17% faster as well because it may depend on how much work the LeetCode server has to do at the moment. One millisecond in either direction can seem like a big difference, but it really isn't IMO. \$\endgroup\$ – Simon Forsberg Dec 12 '17 at 22:53
  • 1
    \$\begingroup\$ I don't know any java, but FWIW this is what I came up with in javascript: maxSum = ary => Math.max(...ary.map(a => a.reduce((acc, x) => acc + x, 0))). Maybe the same idea could be translated to java. \$\endgroup\$ – morbusg Dec 13 '17 at 10:00
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Well, everything points to your answer and my solution. I accept your answer but i'll wait for a few days to see if something new turns up! \$\endgroup\$ – enigma6174 Dec 13 '17 at 10:09
  • \$\begingroup\$ I am finally treating this answer as closed as I now think that your answer is the best out there and your reasoning makes a lot of sense. \$\endgroup\$ – enigma6174 Dec 13 '17 at 19:37
2
\$\begingroup\$

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;
    }
}
\$\endgroup\$
  • \$\begingroup\$ Actually I tried doing something like this but I found out that if all values are negative, the judge expects you to return the highest value. So for an input of {-1,-5}, you must return -1 instead of 0. Therefore you can't just skip all the leading and trailing negative numbers, although you can take the max of all of them and use that as your starting max. When I tried submitting such a solution, my time was worse than the other solution (although I only submitted 2 times). \$\endgroup\$ – JS1 Dec 13 '17 at 10:54
  • \$\begingroup\$ Interesting, and it is rather unfortunate that one small loop is faster than good math. One could remove the posNeg array, and just maintain a positive range sum, and negative range sum. \$\endgroup\$ – Joop Eggen Dec 13 '17 at 11:45
  • \$\begingroup\$ @JS1 yes you are correct. Leading and trailing negatives cannot be ignored, but we can always not add them to the sum as adding negatives to the sum is only going to make it smaller. \$\endgroup\$ – enigma6174 Dec 13 '17 at 19:34
  • \$\begingroup\$ @JoopEggen How do you say your algorithm is a better one than mine? Your's is O(cN) (c being a constant) whereas mine is O(N) and my code is much simpler and shorter. A better algorithm would be faster and more efficient? Also, if the array has all numbers negative or all numbers positive then these are special cases and we can find the solutions very easily. However, to check if the array has all negatives or positives would itself take O(N) time in addition to the extra time. So if there are N input arrays, each check taking O(N) then total would be O(N^2)_ \$\endgroup\$ – enigma6174 Dec 13 '17 at 19:44
  • \$\begingroup\$ It has the same complexity, O(N) == O(cN). But given that your algorith does only two if statements per step it probably is indeed faster: 1 loop of 10 statements <= 10 loops of one statement (so to say). My algorithm would be faster on 1000 negative numbers, as no summing needed. O(N²) is a mistake: the two while loops to determine first and last negative index and then the loop between thow indices, take together O(N): do a ++index N times. The last loop contains 2 loops, on for positives, one for negatives but advance the same index, so do not increase the total number of steps. \$\endgroup\$ – Joop Eggen Dec 14 '17 at 9:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.