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));
}
}