Maximum Subarray (LeetCode Array)

Question: Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.

Idea: Dynamic programing. We can think this problem as dividing the whole array to many disjoint subarrays. Then the result is the maximum of the local sums of these subarrays. So we need to know how to divide the array, or in other words, to find where is the beginning of each disjoint subarray.

Assume F[i-1] is the sum of a subarray starting somewhere (can be anywhere) and ends at index i-1. Now we have array[i] at index i, shall we add i to the existing subarray or start new subarray from i? The answer is if F[i-1] drags down the value of F[i-1]+array[i], we start a new array, otherwise add i to the existing array. For example, array=[-1, 2], we need to start a new array from index 1, since the former sum F[0]=-1 will drags the next maximal sum F[1] down.
Therefore, we have the dynamic programming equation:
F[i]=max(F[i-1]+array[i], array[i]). And the result=max(F[0], F[1], F[2], ... , F[n-1]).

Time: O(n) Space: O(1)

Code: 

 public class Solution {  
   public int maxSubArray(int[] A) {  
     if(A.length==1)  
       return A[0];  
     int preMax=A[0];  
     int maxSoFar=A[0];  
     for(int i=1;i<A.length;i++)  
     {  
       int maxHere=Math.max(preMax+A[i],A[i]);  
       maxSoFar=Math.max(maxSoFar,maxHere);  
       preMax=maxHere;  
     }  
     return maxSoFar;  
   }  
 }