最大子数组和-LeetCode53（经典动态规划）

一、题目描述

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组 是数组中的一个连续部分。

二、算法思想

这是经典的动态规划问题，解该问题的四大基本步骤：

（1）设计状态变量：dp[i]/dp[i][j]。该题设计为dp[i]表示当前以i结尾的子序列的最大值

（2）状态变量的初始变量的赋值。dp[0]=nums[0]

（3）状态转移方程：dp[i]=max(dp[i-1]+nums[i],nums[i]).因为dp[i]为以当前nums[i]结尾的最大子序列，如果dp[i-1]+nums[i]小于nums[i]，说明i前面的数对nums[i]的值起减小作用，所以应当舍弃掉i前面的序列，只取Nums[i]。

三、代码实现

class Solution {
    public int maxSubArray(int[] nums) {
        int sum = 0;
        int len = nums.length;
        //重点：dp[i]表示以i为结尾的子数组最大和！！
        int[] dp = new int[len];
        //初始化
        dp[0] = nums[0];
        for (int i = 1; i < len; i++) {
            //dp[i]要么等于i以及前面所有数之和，要么等于nums[i]（说明前面的数减小了当前以i结尾的子序列的和，所以应当只取Nums[i]）
            dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
        }
        sum = dp[0];
        for (int i = 0; i < len; i++) {
            if (dp[i] > sum) {
                sum = dp[i];
            }
        }
        return sum;
    }