Only one pass to solve the problem

  • 1

    English Version

    First, let's look the picture. When we scan the array from the left to right to get the "Maximum Subarray", the most important is to decide whether the algorithm need to extends the index.
    Follow the idea, we can create a extra space to store the reason, and scan from right to left.
    For example, let's go to the last item, because there're not have any other item in the right, we assign the '0' to the extends[8], which means it's no need to extend from last item. According to the 7th item, we assign the '4' to the extends[7], which means we can increase the final result '4', if we reach the 7th.Then, let's go back to the 6th item, the extends[7] is '4' and the nums[7] is '-5', which means if we extend the index from 7th, the final result will decrese '-1'. Last but not least, let's fouce on the 5th item, the extends[6] is '-1', so we can't extends from the 6th item, the extends[5] is assigned nums[6]. All right, I have explaned all the situations.
    Let's formulate the idea.

    for i  <- nums.length -1 to 0
          if i = nums.length -1
             then  extends[i] = 0
             else {
                       if extends[i + 1] < 0
                          then extends[i] := nums[i+1]
                          else extends[i] := extends[i+1] + nums[i+1]
                          if extends[i] > largestNum 
                              then largestNum := extends[i]

    To be honest, whenthe extends array has been finished, we can get the largestNum.

    The java code.

    public class Solution {
        public int maxSubArray(int[] nums) {
            if(nums.length == 0) return 0;
            if(nums.length == 1) return nums[0];
            int[] extendsArray = new int[nums.length + 1];
            int largestNum = Integer.MIN_VALUE;
            for(int i = nums.length - 1 ; i >= 0 ; i--){
                if( i == nums.length - 1) extendsArray[i] = 0;
                    if(extendsArray[i + 1] < 0) extendsArray[i] = nums[i+1];
                    else extendsArray[i] = extendsArray[i+1] + nums[i+1];
                    if(extendsArray[i] > largestNum) largestNum = extendsArray[i];
            if(extendsArray[0] < 0) extendsArray[nums.length] = nums[0];
            else extendsArray[nums.length] = extendsArray[0] + nums[0];
            if(extendsArray[nums.length] > largestNum) largestNum = extendsArray[nums.length];
            return largestNum;



  • 0

    It is a great idea!!! but it is not completed of your code, lack the extends of first item

    if (extendsArray[0] < 0){
                largestNum = Math.max(nums[0],largestNum);
                largestNum = Math.max(nums[0]+extendsArray[0],largestNum);

    This should be added in the end of your codes.

  • 0

    @superlee828 Thanks for reminding me, I have updated my code.

Log in to reply

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