Only one pass to solve the problem


  • 1
    M

    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.
    0_1475673290555_1.png
    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;
                else{
                    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;
        }
    }
    

    中文版

    这个思路是在路上想出来的,主要是觉得这个不是dp问题,因为没有最优子结构。因此换个角度思考本问题,当我们从左到右到达一个项的时候,我们是否考虑再延伸,肯定是希望下一个项告诉我往它右边延伸还有没有增大项,即当前结果还可以不可以变大。所以我们就从右到左先扫一遍,用一个额外的空间告诉我们是否右边还有增大项。
    0_1475673290555_1.png
    举例说明:
    1、首先最后一项,因为它右边没有元素了,所以我们就认为它的扩展值为0,即不需要扩展。
    2、第7项,我们发现第8项是正值,同时扩展值为0,因此代表我们在第七项的时候应该往第8项扩展,扩展值为4。
    3、第6项,发现第7项的扩展值是4,但是第7项本身的值是-5,因此如果往7扩展,最多得到-5+4=-1,因此第六项的扩展值为-1。
    4、第5项,发现第6项的扩展值为-1,即如果再往后扩展就要变小了,因此不考虑后面的值,第5项的扩展值就是第6项的值。
    综上所示,所有情况已经考虑完毕,代码和算法的形式化如上。同时我们在完成扩展值数组的时候就可以找到最大值,因此每次比较一下即可。


  • 0
    S

    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);
            }
    else{ 
                largestNum = Math.max(nums[0]+extendsArray[0],largestNum);
            }
    

    This should be added in the end of your codes.


  • 0
    M

    @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.