package com.cyf.array;//给定一个整数数组 nums ，找到一个具备最大和的间断子数组（子数组起码蕴含一个元素），返回其最大和。//// 示例://// 输出: [-2,1,-3,4,-1,2,1,-5,4]//输入: 6//解释: 间断子数组 [4,-1,2,1] 的和最大，为 6。///**解题思路 首先能想到的办法是暴力法。 暴力的切分所有可能的子数组，求最大和的数组。 这样做的工夫复杂度是O(n2)，须要两个for循环来实现。 对于面试题目，个别面试官心愿看到的后果都不是暴力法，哪怕是一个dfs剪枝，也要比暴力法好。 这道题目应该应用动静布局来求解，让咱们再来剖析一下这个问题。 在这个问题中，咱们发现，如果咱们从前向后遍历数组，一个子数组的下一个元素是负数，那么退出这个元素肯定是更好的计划。 如果小于零，那么退出这个元素后的子数组肯定不如之前的子数组，之前的子数组就是一个部分最优解。 在整个过程中，咱们去比拟部分最优解中的最大值，就能够失去最优的子数组。 在动静布局题目中，咱们要明确四个因素。 别离是，状态State、转移方程Fuc、初始化Init、后果Ans。 咱们先剖析状态。 咱们应用一个一维数组dp[i]来记录到第i个元素的部分最大值。 接下来是转移方程。 咱们应用 dp[i] = max(dp[i-1] + nums[i], nums[i]) 作为转移方程。 接下来是初始化，咱们另dp[0]等于第一个元素的值，也就是nums[0]。 最初，ans就是整个数组中最大的值。 * @author by cyf * @date 2020/8/25. */public class MaxSubArraySolution { /** * dp[i] 记录到第i个数字的最大序列和 * * @param nums * @return */ public static int maxSubArray(int[] nums) { if (nums.length == 0 && nums ==null ){ return 0; } //初始化dp和max int max = nums[0]; int [] dp = new int[nums.length]; dp[0] = nums[0]; for (int i = 1; i <nums.length ; i++) { dp[i] = Math.max(dp[i-1]+nums[i],nums[i]); max = Math.max(dp[i],max); } return max; } public static void main(String[] args) { int [] nums = {-2,1,-3,4,-1,2,1,-5,4}; System.out.println(MaxSubArraySolution.maxSubArray(nums)); }}