每日一题：给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

2020年11月20日，力扣，简单，最大子序和

一、题目描述

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例：
输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

二、解题思路

一、动态规划思想：若前一个元素大于0，那么将其加到当前元素上

1. 用dp[i]表示第i位结尾的最大子数组的大小
2. 那么当dp[i - 1]小于0的时候，最大子数组就是dp[i] = nums[i]
3. 否则当dp[i - 1]大于0的时候，最大子数组就是dp[i] = dp[i - 1] + nums[i]
4. 每次比较记录好最大和即可

三、实现代码

public class Test1 {
    public static void main(String[] args) {
        int[] arr = {-2,1,-3,4,-1,2,1,-5,4};
        System.out.println("最大和为："+maxSubArray(arr));
    }
    public static int maxSubArray(int[] arr){
        int max = arr[0];  //最大和
        int dp = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (dp <= 0){
                dp = arr[i];
            }else {
                dp = dp + arr[i];
            }
            max = Math.max(max,dp);
        }
        return max;
    }
}