两遍for循环+dp数组时间，所以时间复杂度是N,空间是N

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

将第二个for循环优化到第一个for循环中，时空复杂度不变

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

由于状态只和dp[i-1]有关，可以优化到只有一个变量，时间复杂度是N，空间是1

public int maxSubArray(int[] nums) {
    int max=nums[0],st=nums[0];
    for(int i=1;i<nums.length;i++)
    {
        st=Math.max(nums[i],st+nums[i]);
        max=Math.max(max,st);
    }
    return max;
}