给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-subarray
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
算法一：动态规划，创建二维数组，每个数组中保存m到n的合计，最后获得二维数组中的最大值，在leetcode中超出内存～～～
public static int maxSubArray(int[] nums) { int sum = Integer.MIN_VALUE; int[][] dp = new int[nums.length + 1][nums.length + 1]; dp[0][0] = nums[0]; for (int i = 0; i < nums.length; i++) { dp[i][i] = nums[i]; sum = Math.max(dp[i][i], sum); } for (int i = 0; i < nums.length; i++) { for (int j = i + 1; j < nums.length; j++) { dp[i][j] = dp[i][j - 1] + nums[j]; sum = Math.max(dp[i][j], sum); } } for (int i = 0; i < nums.length; i++) { for (int j = 0; j < nums.length; j++) { System.out.print(dp[i][j] + " "); } System.out.println(); } return sum; }
算法二：暴力循环，算法在leetcode中时间超时～～
public static int maxSubArray1(int[] nums) { int sumInt = Integer.MIN_VALUE; for (int i = 0; i < nums.length; i++) { for (int j = i; j < nums.length; j++) { sumInt = Math.max(sum(nums, i, j), sumInt); } } return sumInt; } public static int sum(int[] nums, int start, int end) { int sum = 0; for (int i = start; i <= end; i++) { sum += nums[i]; } return sum; }
算法三
原文：https://www.cnblogs.com/use-D/p/13387231.html