Leetcode面试经典150题-53.最大子数组和

 解法都在代码里，不懂就留言或者私信

相对简单的题、经典动态规划的方案

class Solution {
    /**这个题是再简单不过的动态规划了，我们定义一个动态规划数组dp,dp[i]表示以i位置结尾的最大子数组和（i位置必须要）
    从以所有位置结尾的最大子数组和里找最大值就是我们的答案 */
    public int maxSubArray2(int[] nums) {
        if(nums == null || nums.length == 0) {
            return 0;
        }
        if(nums.length == 1) {
            return nums[0];
        }
        /**定义动态规划数组dp,dp[i]表示以i位置结尾的最大子数组和（i位置必须要）*/
        int[] dp = new int[nums.length];
        /**0位置必须要，以它结尾最长也就是一个数，所以别无选择 */
        dp[0] = nums[0];
        int maxSum = dp[0];
        for(int i = 1;i < dp.length; i++) {
            /**前面能出正数就要，不能出就不要 */
            dp[i] = dp[i-1] > 0? dp[i-1] + nums[i] : nums[i];
            maxSum = Math.max(maxSum, dp[i]);
        }
        return maxSum;
    }

    public int maxSubArray(int[] nums) {
        if(nums == null || nums.length == 0) {
            return 0;
        }
        if(nums.length == 1) {
            return nums[0];
        }
        /**动态规划的过程省略，我们只用一个遍历pre代表以它前面那个数结尾的最大和 */
        /**0位置必须要，以它结尾最长也就是一个数，所以别无选择 */
        int pre = nums[0];
        int maxSum = pre;
        for(int i = 1;i < nums.length; i++) {
            /**前面能出正数就要，不能出就不要 */
            pre = nums[i] + Math.max(pre, 0);
            maxSum = Math.max(maxSum, pre);
        }
        return maxSum;
    }
}