package normal; /** * @program JavaBooks * @description: 53. 最大子序和 * @author: mf * @create: 2019/11/10 10:37 */ /* 题目：https://leetcode-cn.com/problems/maximum-subarray/ 类型：动态规划 难度：easy */ /* 输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。 */ public class MaxSubArray { public static void main(String[] args) { int[] nums = {-2,1,-3,4,-1,2,1,-5,4}; System.out.println(maxSubArray(nums)); } public static int maxSubArray(int[] nums) { if (nums == null || nums.length == 0) return 0; int max = nums[0]; // 记录包含arr[i]的连续子数组的和的最大值 int ans = nums[0]; // 记录当前所有子数组的和的最大值 for (int i = 1; i < nums.length; i++) { max = Math.max(max + nums[i], nums[i]); ans = Math.max(max, ans); } return ans; } }