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)。
3. 完整代码
#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; } } }