O(n) AC JavaCode


  • 1
    X

    Optimal Structure

    • Subproblem: t[i] is the maximum sum when the subsequence ends at ith element
        Recurrence: t[i] = max(A[i],A[i]+t[i-1])
                             if A[i] is larger, it means the last sequence ends and an new one starts
                             if A[i]+t[i-1 is larger, it means the last sequence increases
        Base Cases: t[0] = 0 which means sum of no element is 0
    
    • Here is the code

       public int maxSubArray(int[] A) {
           
           int[] t = new int[A.length+1];
           
           t[0] = 0;
           int max = Integer.MIN_VALUE;
           
           for(int i = 1; i <= A.length;i++){
               
               t[i] = Math.max(A[i-1],A[i-1] + t[i-1]);
               max = Math.max(t[i],max);
           }
           
           return max;
       }

  • 0
    P

    You are really helpful, and the solution is neat and clear! Thank you!


Log in to reply
 

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