示例 1 :

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

解法一、三重for循环

解题思路： 通过前两层for循环找出数组的所有组合，第三层for循环计算该组合的sum，如果大于max，则赋值给max。
  时间复杂度是O(N3),空间复杂度是O(1)。

public int maxSubArray(int[] nums) {int max_res = Integer.MIN_VALUE;for(int i = 0; i < nums.length; i++) {for(int j = i; j < nums.length; j++) {int thisSum = 0;for(int k = i; k <= j; k++) {thisSum += nums[k];}if(max_res < thisSum) {max_res = thisSum;}}}return max_res;}

额外补充：Java基本类型最大最小值的表示：

fmax = Float.MAX_VALUE;fmin = Float.MIN_VALUE;dmax = Double.MAX_VALUE;dmin = Double.MIN_VALUE;bmax = Byte.MAX_VALUE;bmin = Byte.MIN_VALUE;cmax = Character.MAX_VALUE;cmin = Character.MIN_VALUE;shmax = Short.MAX_VALUE;shmin = Short.MIN_VALUE;imax = Integer.MAX_VALUE;imin = Integer.MIN_VALUE;lmax = Long.MAX_VALUE;lmin = Long.MIN_VALUE;

解法二、二重for循环

解题思路： 该方法是用两层循环，不用特地用第三层循环计算，不然会导致大量的重复计算。
  时间复杂度是O(N2),空间复杂度是O(1)。

public int maxSubArray(int[] nums) {int max_res = Integer.MIN_VALUE;for(int i = 0; i < nums.length; i++) {int thisSum = 0;for(int j = i; j < nums.length; j++) {thisSum += nums[j];if(max_res < thisSum) {max_res = thisSum;}}}return max_res;}

解法三、分治策略

解题思路： 将数组从中间分为两部分，容易看出来，最长子序列和可能存在在三个地方：左边，右边或者是中间，通过递归的方式就可以求出最长子序列和了。
  时间复杂度是O(NlogN),空间复杂度是O(1)。

static int maxSum(int[] nums, int left, int right) {if(left == right) {return nums[left];}int mid = (left + right) / 2;//求左边的最长子序和int maxLeftSum = maxSum(nums, left, mid);//求右边的最长子序和int maxRightSum = maxSum(nums, mid+1, right);//求中间到两边的最长子序列和//因为最小的数不知道多小，所以一开始初试为INT的最小值int maxLeftBorderSum = Integer.MIN_VALUE;int maxRightBorderSum = Integer.MIN_VALUE;int temp = 0;//左边那块从右边开始找for(int i = mid; i >= left; i--) {temp += nums[i];if(maxLeftBorderSum < temp) {maxLeftBorderSum = temp;}}temp = 0;//右边那块从左边开始找for(int i = mid + 1; i <= right; i++) {temp += nums[i];if(maxRightBorderSum < temp) {maxRightBorderSum = temp;}}System.out.println(maxLeftBorderSum + maxRightBorderSum+"  "+maxRightSum+"  "+maxLeftSum);//计算三者的最大值return Math.max(maxLeftBorderSum + maxRightBorderSum, Math.max(maxRightSum, maxLeftSum));}public int maxSubArray(int[] nums) {return maxSum(nums, 0, nums.length-1);}

解法四、规律

解题思路： 一次循环，只对数据进行一次扫描，开始累加，一开始是正的，如果加上这个数变成了负数，说明该数是负的，则归零。
  时间复杂度是O(N),空间复杂度是O(1)。

  public int maxSubArray(int[] nums) {int maxSum = Integer.MIN_VALUE;int thisSum = 0;for(int i = 0; i < nums.length; i++) {thisSum += nums[i];if(maxSum < thisSum) {maxSum = thisSum;}if(thisSum < 0) {thisSum = 0;}}return maxSum;}

总结：解决一道题有多种解法，只要你耐心去做就会收获很大，有的解法虽然能够通过，但面对大量输入时，可能就是无法应用，无论是空间复杂度还是时间复杂度，都值得我们考虑。