"What is the fastest solution for finding the maximum sum of a subarray?" 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 &lt; size; i++)
        {
            if (sum &lt; 0)
                sum = 0;

            sum += nums[i];
            if (sum &gt; 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?
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 &lt; size; i++)
        {
            sum += nums[i];
            if (sum &gt; max)
                max = sum;
            if (sum &lt; 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.