这次的课上问题是算法中的一道经典例题，如果只是最简单的解决方式就是暴力解决，但如果加上O（n）复杂度的条件，问题难度会有所上升，所以在此记录下该问题的解决方式，拓展自己对算法设计的知识面。
问题描述
给定一个整数数组
nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。示例:
输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
个人理解——最开始看到这题的时候迷迷糊糊想睡觉，课上还有点丢脸，就不提了。首先想法是归并，想把正负连续子数组合起来去找规律，但最后实在找不出规律，正负合并也不能找出规律，如果这样算下去和暴力破解没什么区别。在网上找解决方法后，发现用递归的话不仅能做到O（n）复杂度而且算法简单易懂，在运用分治算法或者动态规划就能很完美的解决问题。之后在了解了解决方法后自己再完成代码，就容易多了。
相对容易的分治法
核心思想——就是分而治之，把大问题化成小问题。把数组A[ ]尽可能分成大小相同的两个数组，然后最大子数组{ A[i],…,A[j] }{只用可能分为三种情况——
1.完全位于子数组A[low..mid]中， 因此low<=i<=j<=mid;
2.完全位于子数组A[mid + 1..high]中，因此mid<=i<=j<=high;
3.跨越了中点，因此low<=i<=mid<j<=high;
由此完成的递归算法如下。
public class DivideAndConquer { int FindMaxCrossSubarray(int[] A, int low, int mid, int high) { int left_sum = -1000000000; int sum = 0; for (int i = mid; i >= low; i--) { sum += A[i]; if (sum > left_sum) { left_sum = sum; } } int right_sum = -100000000; sum = 0; for (int i = mid + 1; i <= high; i++) { sum += A[i]; if (sum > right_sum) { right_sum = sum; } } return left_sum + right_sum; } int FindMaxSubarray(int A[], int low, int high) { int left_sum, right_sum, cross_sum; if (high == low) { return A[low]; } else { int mid = (low + high) / 2; left_sum = FindMaxSubarray(A, low, mid); right_sum = FindMaxSubarray(A, mid + 1, high); cross_sum = FindMaxCrossSubarray(A, low, mid, high); if (left_sum >= right_sum && left_sum >= cross_sum) return left_sum; else if (right_sum >= left_sum && right_sum >= cross_sum) return right_sum; else return cross_sum; } } public static void main(String[] args) { int[] a = { 13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7 }; int length = a.length; DivideAndConquer b = new DivideAndConquer(); System.out.println(b.FindMaxSubarray(a, 0, length - 1)); }
} 原文：https://blog.csdn.net/xjm199/article/details/17954997
具体化过程时我发现和暴力破解一样都是求出了所有子数组的和，但分而治之的方法让它省下来很多对比运算和遍历过程，所以复杂度为T( n ) = 2 T( n / 2 ) + O( 1 ) ≈O（n）
动态划分法
由于前者是递归而且本质并没有改变，所以时间复杂度还是很大，但动态划分不一样，这个思路很简单，只需要一遍遍历就行。
如果我们计算了A[0~i]的数组和发现和小于0且最大子数组不在里面，那么就很容易得知最大子数组一定不包含A[0~i]，那么舍弃掉即可，从A[i+1]再开始寻找即可，直到取完。
下面是我写过一遍代码。
public int FindMaxSubArray(int[] a) { int n = a.length; int[] dp = new int[n]; dp[0] = a[0]; int sum = dp[0]; for(int i = 1; i < n; i++){ dp[i] = a[i] + (dp[i - 1] > 0 ? dp[i - 1] : 0); sum = Math.max(sum, dp[i]); } return sum; }
原作者FujiwaranoSai