package com.ljp.test.leetcode;
/**
* <b>53. 最大子数组和
*
*
* 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
*
* 子数组 是数组中的一个连续部分。
*
*
* 示例 1：
*
* 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
* 输出：6
* 解释：连续子数组[4,-1,2,1] 的和最大，为6 。
* 示例 2：
*
* 输入：nums = [1]
* 输出：1
* 示例 3：
*
* 输入：nums = [5,4,-1,7,8]
* 输出：23
*
* 提示：
*
* 1 <= nums.length <= 105
* -104 <= nums[i] <= 104
*
* 进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
*
* 来源：力扣（LeetCode）
* 链接：<a href="https://leetcode.cn/problems/maximum-subarray">53. 最大子数组和
* 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*
* @author luojunping
* @since 2023-03-07
*/
public class Number0053{
public static void main(String[] args) {
int[] nums1 ={-2, 1, -3, 4, -1, 2, 1, -5, 4};
int[] nums2 ={1};
int[] nums3 ={5, 4, -1, 7, 8};
System.out.println(DynamicPlanning.sumMaxSubArray(nums1));
System.out.println(DynamicPlanning.sumMaxSubArray(nums2));
System.out.println(DynamicPlanning.sumMaxSubArray(nums3));
}
/**
* 动态规划
* 三大步骤：
* 1、定义数组元素的含义：preSumMax：前一下标最大子数组, finalSumMax：当前下标最大子数组和
* 2、找出数组元素之间的关系式：preSumMax = Math.max(preSumMax + nums[i], nums[i]) finalSumMax = Math.max(finalSumMax, preSumMax)
* 3、找出初始值：int preSumMax = nums[0], finalSumMax = nums[0]
*/
private static class DynamicPlanning{
public static int sumMaxSubArray(int[] nums) {
int preSumMax = nums[0], finalSumMax = nums[0];
for (int i =1, length = nums.length; i < length; i++) {
preSumMax = Math.max(preSumMax + nums[i], nums[i]);
finalSumMax = Math.max(finalSumMax, preSumMax);
}
return finalSumMax;
}
}
}
