1、題目描述
給定一個整數數組 nums?，找到一個具有最大和的連續子數組（子數組最少包含一個元素），返回其最大和。
示例:
輸入: [-2,1,-3,4,-1,2,1,-5,4],
輸出: 6
解釋:?連續子數組?[4,-1,2,1] 的和最大，為?6。
2、解法及解題思路
public class MaximumSubarray {public static void main(String[] args) {int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};// int[] nums = {-1, -3, -4, 4, -2, -1, -5, -4};System.out.println(maxSubArray(nums));System.out.println(maxSubArray1(nums));}/*** 解法一 動態規劃（Kadane 算法）** @param nums* @return*/private static int maxSubArray(int[] nums) {// 迄今為止的最大和int res = nums[0];// 前一元素位置的最大和int sum = 0;for (int num : nums) {if (sum > 0) {// 如果 sum > 0，則說明 sum 對結果有增益效果，則 sum 保留并加上當前遍歷數字sum += num;} else {// 如果 sum <= 0，則說明 sum 對結果無增益效果，需要舍棄，則 sum 直接更新為當前遍歷數字sum = num;}// 每次比較 sum 和 res的大小，將最大值置為res，遍歷結束返回結果res = Math.max(res, sum);}return res;}/*** 解法二 貪心算法** @param nums* @return*/private static int maxSubArray1(int[] nums) {// 當前元素位置的最大和int curMax = nums[0];// 迄今為止的最大和int soFarMax = nums[0];for (int i = 1; i < nums.length - 1; i++) {curMax = Math.max(curMax, curMax + nums[i]);soFarMax = Math.max(soFarMax, curMax);}return soFarMax;}}?
