1. 题目描述(LeetCode53) Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [-2,1,-3,4,-1,2,1,-5,4], the contiguous subarray [4,-1,2,1] has the largest sum = 6.
More practice: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
2. 解决思路 这是一个非常经典的算法题，在网上搜了一篇用线性时间解决这个问题的比较详细的博客，现将博客中自己认为比较重要和难理解的证明摘录如下：
假设使用穷举法，则至少须要O(n^2)的时间才干得到答案。卡耐基梅隆大学的Jay Kadane的给出了一个线性时间算法（时间复杂度为O(n)），我们就来看看。怎样在线性时间内解决最大子串和问题。 要说明Kadane算法的正确性，须要两个结论。 首先。对于array[1…n]，假设array[i…j]就是满足和最大的子串，那么对于不论什么k(i<=k<=j)，我们有array[i…k]的和大于0。因为假设存在k使得array[i…k]的和小于0。那么我们就有array[k+1…j]的和大于array[i…j]，这与我们假设的array[i…j]就是array中和最大子串矛盾。
其次，我们能够将数组从左到右切割为若干子串，使得除了最后一个子串之外，其余子串的各元素之和小于0，且对于全部子串array[i…j]和随意k（i<=k
#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> void MaxSubSum(int *arr, int len, int &l, int &r); int main() { int* arr = NULL; //存储数组 int len = 0; printf("请输入数组的长度：\n"); scanf("%d", &len); while (len <= 0) { printf("长度必须大于0，请重新输入：\n"); scanf("%d", &len); } arr = (int*)malloc(sizeof(int)* len); //数组分配内存 printf("请输入数组的每一位数：\n"); for (int i = 0; i<len; ++i) { scanf("%d", &arr[i]); } //调用封装好的功能函数 int l, r; MaxSubSum(arr, len, l, r); //输出结果 printf("新的数组长度为: %d\n", r - l + 1); printf("和最大的连续子数组元素为:\n"); for (int i = l; i <= r; ++i) { printf("%d ", arr[i]); } scanf("%d", &len); //加个输入让窗口停下来 free(arr); //释放内存 return 0; } void MaxSubSum(int *arr, int len, int &l, int &r) { int i; int MaxSum = 0; int CurSum = 0; int ll = -1; for (i = 0; i < len; i++) { CurSum += arr[i]; if (CurSum > MaxSum) { MaxSum = CurSum; l = ll + 1; r = i; } //如果累加和出现小于0的情况 //则和最大的子序列肯定不可能包含前面的元素 //这时累加和置零，从下个元素重新开始累加 if (CurSum <= 0) { CurSum = 0; ll = i; } } }