53. 最大子序和

解题思路

1.最简单的解法
双层for循环，有一个用于标记、一个用于循环，做加法，然后判断与临时变量sum的大小
2.第二种解法（DP）
去除一层for循环，推导出状态转移方程，f(i)=max{f(i−1)+nums[i],nums[i]}

解题遇到的问题

1.第一种解法，以时间换空间，时间复杂度为O（n^2），空间复杂度O（1）
2.第二种解法，时间复杂度为O（n），空间复杂度O（1）

后续需要总结学习的知识点

1.动态规划思想、状态转移方程如何推导

##解法1
class Solution {
   public static int maxSubArray(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }

        int sum = nums[0];
        for (int i = 0; i < nums.length; i++) {
            int a = 0;
            for (int j = i; j < nums.length; j++) {
                a += nums[j];
                if (a > sum) {
                    sum = a;
                }
            }
        }
        return sum;
    }
}

##解法2
class Solution {
    public static int maxSubArray(int[] nums) {
        int sum = nums[0];
        int pre = 0;
        for (int i = 0; i < nums.length; i++) {
            pre = Math.max(nums[i], pre + nums[i]);
            sum = Math.max(pre, sum);
        }
        return sum;
    }
}