给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
推荐参考：https://blog.csdn.net/zwzsdy/article/details/80029796；https://blog.csdn.net/u014472643/article/details/81097672
1 public class MaxSubArray { 2 //方法一：扫描法，从头遍历数组，对于数组中每一个元素，要么加入之前的数组（加入其它组），要么自己开始（单开一组） 3 //如果之前的组结果为负，则应该自己开始一个新的组，因为自己的值比加入后的值还要大。O(N) 4 public int maxSubArray1(int[] array) { 5 if(array.length == 0) { 6 throw new IllegalArgumentException("输入参数错误"); 7 } 8 if(array.length == 1) { 9 return array[0]; 10 } 11 int len = array.length; 12 int[] res = new int[len]; 13 res[0] = array[0]; 14 int max = res[0]; 15 for(int i=1; i<len; i++) { 16 //数组res记录连续数组的和，如果大于0，则加入该连续数组，小于0，重新开始新的连续数组 17 if(res[i-1] > 0) { 18 res[i] = res[i-1] + array[i]; 19 }else { 20 res[i] = array[i]; 21 } 22 max = Math.max(res[i], max); 23 } 24 return max; 25 } 26 //方法二：暴力法，依次计算每个子数组的和，选择其中最大的子数组，时间复杂度为n^3 27 public int maxSubArray2(int[] array) { 28 if(array.length == 0) { 29 throw new IllegalArgumentException("输入参数错误"); 30 } 31 int len = array.length; 32 int sum = 0; 33 int max = array[0]; //只有一个元素时最大值即为该元素 34 for(int i=0; i<len; i++) { 35 for(int j=i; j<len; j++) { //单个元素也是子数组，需要包括 36 for(int k=i; k<=j; k++) { 37 sum += array[k]; 38 } 39 if(sum > max) { 40 max = sum; 41 } 42 sum = 0; 43 } 44 } 45 return max; 46 } 47 //方法二：暴力法改进，在第三层循环中，每次都要计算上次已经计算的序列，发生了重复计算，所以可以在前一次的计算的基础上 48 //相加，减少一层循环，时间复杂度为n^2 49 public int maxSubArray22(int[] array) { 50 if(array.length == 0) { 51 throw new IllegalArgumentException("输入参数错误"); 52 } 53 int len = array.length; 54 int sum = 0; 55 int max = array[0]; 56 for(int i=0; i<len; i++) { 57 for(int j=i; j<len; j++) { 58 sum += array[j]; 59 if(sum > max) { 60 max = sum; 61 } 62 } 63 sum = 0; 64 } 65 return max; 66 } 67 //方法三：分治法，将整个数组一直拆分至单个元素，从下往上得到最大值。 68 //把数组分成两个序列，最大连续子序列和要么在左半部分，要么在右半部分，要么是横跨左右部分 69 public int maxSubArray3(int[] array) { 70 if(array.length == 0) { 71 throw new IllegalArgumentException("输入参数错误"); 72 } 73 return maxSubArrayPart(array, 0, array.length - 1); 74 } 75 private int maxSubArrayPart(int[] array, int left, int right) { 76 //递归出口 77 if(left == right) { 78 return array[left]; 79 } 80 int mid = (left + right) / 2; 81 //左半部分最大值 82 int maxLeft = maxSubArrayPart(array, left, mid); 83 //右半部分最大值 84 int maxRight = maxSubArrayPart(array, mid+1, right); 85 86 //跨边界最大值，必定包括左半部分的最后一个元素，以及右半部分的第一个元素 87 //边界以左 88 int sum = 0; 89 int maxLeftBorder = array[mid]; 90 for(int i=mid; i>=left; i--) { 91 sum += array[i]; 92 if(sum > maxLeftBorder) { 93 maxLeftBorder = sum; 94 } 95 } 96 //边界以右 97 sum = 0; 98 int maxRightBorder = array[mid+1]; 99 for(int i=mid+1; i<=right; i++) { 100 sum += array[i]; 101 if(sum > maxRightBorder) { 102 maxRightBorder = sum; 103 } 104 } 105 int maxBorder = maxLeftBorder + maxRightBorder; 106 // return Math.max(Math.max(maxRight, maxLeft), maxBorder); //两者皆可 107 return (maxRight>maxLeft) ? (maxRight>maxBorder ? maxRight : maxBorder) 108 : (maxLeft>maxBorder ? maxLeft : maxBorder); 109 } 110 111 //方法四：动态规划（动态规划三要素：最优子结构(递归方程)、边界条件(终止条件)和状态转移方程(前两者总结)） 112 //对于第i个元素，有两种选择，要么加入已存在的连续子数组，要么只包括自己开启新的连续子数组。判断条件是前面已经 113 //存在的连续子数组和是否大于0。 114 //状态转移方程：dp = max[arr[i], arr[i] + sum] 115 public int maxSubArray4(int[] array) { 116 //边界条件 117 int sum = array[0]; 118 119 int result = array[0]; 120 for(int i=1; i<array.length; i++) { 121 if(sum > 0) { 122 sum += array[i]; 123 }else { 124 sum = array[i]; 125 } 126 if(sum > result) { 127 result = sum; 128 } 129 } 130 return result; 131 } 132 133 }