初学者，自己写了个比较简单的最大子数组问题算法，仅供参考。
#include &iostream&
int subarray(int a[], int left, int right)
int sum = INT_MIN;
int temp = 0;
for (int i = i &= i++)
temp += a[i];
if (temp & sum)
if (temp & 0)
int main()
int a[] = { 0,-1,1,1,-6,-7 };
std::cout && subarray(a, 0, 5)&&'\n';
&如果数组全为负数，则返回最大的那个负数，可以在return前对sum判断，选择返回0。
如果需要最大子数组的左右索引，可以使用结构。
&&相关文章推荐
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：21次
排名：千里之外一、第三章简单回顾　
　　中间略过了第三章，&第三章主要是介绍如何从数学层面上科学地定义算法复杂度，以致于能够以一套公有的标准来分析算法。其中，我认为只要记住三个符号就可以了，其他的就看个人情况，除非你需要对一个算法剖根问底，不然还真用不到，我们只需有个印象，知道这玩意是用来分析算法性能的。三个量分别是：确定一个函数渐近上界的&O符号，渐近下届&O符号，以及渐近紧确界&T符号，这是在分析一个算法的界限时常用的分析方法，具体的就详看书本了，对于我们更多关注上层算法的表达来说，这些显得不是那么重要，我的理解是&O可以简单看成最坏运行时间，&O是最好运行时间，&T是平均运行时间。一般我们在写一个算法的运行时间时，大多是以&T符号来表示。参考下面这幅经典的图：
二、第四章两大板块
　　第四章讲递归，也是数学的东西太多了，我准备这样来组织这章的结构：先用一个例子（最大子数组和）来讲解用到递归的一个经典方法&&分治法，然后在引入如何解递归式，即引入解递归式的三种方法。
1、由分治法引发的
&这一章提出了一个在现在各大IT公司在今天依然很喜欢考的一道笔试面试题：
求连续子数组的最大和
题目描述：
输入一个整形数组，数组里有正数也有负数。
数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。
求所有子数组的和的最大值。要求时间复杂度为O(n)。
例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，
因此输出为该子数组的和18。
要求时间复杂度是O(n)，我们暂且不管这个，由浅入深地分析一下这道题，时间复杂度从O(n^2)-&O(nlgn)-&O(n)。
1）、第一，大部分人想到的肯定是暴力法，两个for循环，时间复杂度自然是O(n^2)，如下：
1 /************************************************************************/
3 /************************************************************************/
4 void MaxSubArraySum_Force(int arr[], vector&int& &subarr, int len)
if (len == 0)
int nMax = INT_MIN;
int low = 0, high = 0;
for (int i = 0; i & i ++) {
int nSum = 0;
for (int j = j & j ++) {
nSum += arr[j];
if (nSum & nMax) {
for (int i = i &= i ++) {
subarr.push_back(arr[i]);
2）、第二，看了《算法导论》，你可能会想到分治法，看完之后你肯定会为该分治思想而惊叹，尤其是&横跨中点&的计算思想。简单说下该分治思想，其实很简单，最大和子数组无非有三种情况：左边，右边，中间。
时间复杂度分析：
　　根据分治的思想，时间复杂度的计算包括三部分：两边+中间。由于分治的依托就是递归，我们可以写出下面的递推式（和合并排序的递推式是一样的）：
其中的&T(n)为处理最大和在数组中间时的情况，经过计算（怎么计算的，请看本节第二部分：解分治法的三种方法），可以得到分治法的时间复杂度为&T(nlgn)。代码如下：
1 /************************************************************************/
最大和子数组有三种情况：
1)A[1...mid]
2)A[mid+1...N]
3)A[i..mid..j]
7 /************************************************************************/
8 //find max crossing left and right
9 int Find_Max_Crossing_Subarray(int arr[], int low, int mid, int high)
const int infinite = -9999;
int left_sum =
int right_sum =
int max_left = -1, max_right = -1;
int sum = 0; //
for (int i = i &= i --) {
sum += arr[i];
if (sum & left_sum) {
left_sum =
max_left =
//from mid to right
for (int j = mid + 1; j &= j ++) {
sum += arr[j];
if (sum & right_sum) {
right_sum =
max_right =
return (left_sum + right_sum);
36 int Find_Maximum_Subarray(int arr[], int low, int high)
if (high == low) //
return arr[low];
int mid = (low + high)/2;
int leftSum = Find_Maximum_Subarray(arr, low, mid);
int rightSum = Find_Maximum_Subarray(arr, mid+1, high);
int crossSum = Find_Max_Crossing_Subarray(arr, low, mid, high);
if (leftSum &= rightSum && leftSum &= crossSum)
return leftS
else if (rightSum &= leftSum && rightSum &= crossSum)
return rightS
return crossS
3）、第三，看了《算法导论》习题4.1-5，你又有了另外一种思路：数组A[1...j+1]的最大和子数组，有两种情况：a) A[1...j]的最大和子数组;&b) 某个A[i...j+1]的最大和子数组，假设你现在不知道动态规划，这种方法也许会让你眼前一亮，确实是这么回事，恩，看代码吧。时间复杂度不用想，肯定是O(n)。和暴力法比起来，我们的改动仅仅是用一个指针指向某个使和小于零的子数组的左区间（当和小于零时，区间向左减小，当和在增加时，区间向右增大）。因此，我们给这种方法取个名字叫区间法。
1 /************************************************************************/
求A[1...j+1]的最大和子数组，有两种情况：
1)A[1...j]的最大和子数组
2)某个A[i...j+1]的最大和子数组
6 /************************************************************************/
7 void MaxSubArraySum_Greedy(int arr[], vector&int& &subarr, int len)
if (len == 0)
int nMax = INT_MIN;
int low = 0, high = 0;
int cur = 0; //一个指针更新子数组的左区间
int nSum = 0;
for (int i = 0; i & i ++) {
nSum += arr[i];
if (nSum & nMax) {
if (nSum & 0) {
for (int i = i &= i ++)
subarr.push_back(arr[i]);
第四，你可能在平常的学习过程中，听说过该问题最经典的解是用动态规划来解，等你学习之后，你发现确实是这样，然后你又一次为之惊叹。动态规划算法最主要的是寻找递推关系式，大概思想是这样的：数组A[1...j+1]的最大和：要么是A[1...j]+A[j+1]的最大和，要么是A[j+1]，据此，可以很容易写出其递推式为：
sum[i+1] = Max(sum[i] + A[i+1], A[i+1])
化简之后，其实就是比较sum[i] ?& 0（sum[i] + A[i+1]&?& A[i+1]）,由此，就很容易写出代码如下：
1 /************************************************************************/
动态规划（对应着上面的贪心法看，略有不同）
求A[1...j+1]的最大和子数组，有两种情况：
1)A[1...j]+A[j+1]的最大和子数组
dp递推式：
sum[j+1] = max(sum[j] + A[j+1], A[j+1])
8 /************************************************************************/
9 int MaxSubArraySum_dp(int arr[], int len)
if (len &= 0)
int nMax = INT_MIN;
int sum = 0;
for (int i = 0; i & i ++) {
if (sum &= 0)
sum += arr[i];
sum = arr[i];
if (sum & nMax)
　　可以看出，区间法和动态规划有几分相似，我觉得两种方法的出发点和终点都是一致的，只不过过程不同。动态规划严格遵循递推式，而区间法是寻找使区间变化的标识，即和是否小于零，而这个标识正是动态规划采用的。
　　由于光这一部分就已经写得足够长了，为了方便阅读，所以本节第二部分：解递归式的三种方法 转
阅读(...) 评论()算法导论（6）
题目：使用如下思想为最大子数组问题设计一个非递归的、线性时间的算法、从数组的左边界开始，右左至右处理，记录最大子数组
public class Find_Max_SubArray {
public static void main(String[] args) {
int A[] = { -12, 12, 12, -2, 12, -120, 120 , 123 ,-1230 };
Find_Max_SubArray(A);
public static void Find_Max_SubArray(int A[]) {
// 记录相加的和
int sum = 0;
// 记录最大值
int max = 0;
// 记录最大子数组左下标
int indexLeft = 0;
// 记录最大子数组右下标
int indexRight = 0;
// 用来标记tempsum是否重新初始化
int mark = 0;
// 用来记录左下标加了多少次
int tempSum = 0;
for (int i = 0; i & A. i++) {
sum += A[i];
// 如果sum&0,说明A[i,j]这段已经没有继续加的必要，
if (sum & 0) {
// 重新初始化sum
// mark=1，让tempsum重新计数
if (sum & max) {
// 将最新的最大值赋予max
// 记录数组右下标
indexRight =
// 判断tempsum是否需要重新计数
if (mark == 1) {
tempSum = -1;
tempSum++;
// 算出数组做下标
indexLeft = indexRight - tempS
System.out.print(&最大子数组和为& + max + &，下标[& + indexLeft + &,&
+ indexRight + &]&);
------------------------------------------------------------------------------------------------苦难不是博得同情的资本，唯有不断奋斗才能改变命运！
&&相关文章推荐
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：28118次
排名：千里之外
原创：66篇
转载：19篇
(1)(1)(16)(24)(6)(32)(1)(4)算法导论第三版4.1最大和子数组思考
算法导论第三版4.1最大和子数组思考
发布时间： 8:29:13
编辑：www.fx114.net
本篇文章主要介绍了"算法导论第三版4.1最大和子数组思考"，主要涉及到算法导论第三版4.1最大和子数组思考方面的内容，对于算法导论第三版4.1最大和子数组思考感兴趣的同学可以参考一下。
对于maximum_subarray的分治算法：
#include &stdio.h&
#include &stdlib.h&
#include &iostream&
#include &limits.h&
int max_crossing_subarray(int A[], int low, int mid, int high, int& sub_low, int& sub_high)
int sum = 0;
int left_sum = INT_MIN, right_sum = INT_MIN;
int left_low, right_
for(i = i&= i--)
sum += A[i];
if(left_sum & sum)
left_sum =
left_low =
for(i = i&= i++)
sum += A[i];
if(right_sum & sum)
right_sum =
right_high =
sum = left_sum + right_sum - A[mid];
sub_low = left_
sub_high = right_
int max_subarray(int A[], int low, int high, int& sub_low, int& sub_high)
int sum = 0;
int mid = (low + high)/2;
if(low == high)
sum = A[low];
sub_low = sub_high =
int sum1,sum2, sum3;
sum1 = max_subarray(A, low, mid, sub_low, sub_high);
int low1 = sub_
int high1 = sub_
sum2 = max_subarray(A, mid+1, high, sub_low, sub_high);
int low2 = sub_
int high2 = sub_
sum3 = max_crossing_subarray(A, low, mid, high, sub_low, sub_high);
int low3 = sub_
int high3 = sub_
if(sum3 & sum1 && sum3&sum2)
sub_low = low3;
sub_high = high3;
return sum3;
if(sum1 & sum2)
sub_low = low1;
sub_high = high1;
return sum1;
sub_low = low2;
sub_high = high2;
return sum2;
void main()
int A[] = {13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7};
int& sub_low =
int& sub_high =
cout&&max_subarray(A, 0, 15, sub_low, sub_high)&&
cout&&sub_low&&
cout&&sub_high&&
其中要注意的是如何求跨边界的最大和子数组。我一开始认为跨边界最大子数组就是左边最大和开始的索引到右边最大和结束的索引之间的数的和，错误代码如下：
#include &stdio.h&
#include &stdlib.h&
#include &iostream&
int max_subarray(int A[], int low, int high, int& sub_low, int& sub_high)
int sum = 0;
int mid = (low + high)/2;
if(low == high)
sum = A[low];
sub_low = sub_high =
int sum1,sum2;
sum1 = max_subarray(A, low, mid, sub_low, sub_high);
int low1 = sub_
int high1 = sub_
sum2 = max_subarray(A, mid+1, high, sub_low, sub_high);
int low2 = sub_
int high2 = sub_
for(int i = low1; i&= high2; i++)
sum += A[i];
if(sum & sum1 && sum&sum2)
sub_low = low1;
sub_high = high2;
if(sum1 & sum2)
sum = sum1;
sub_low = low1;
sub_high = high1;
cout&&sub_low&&& &&&sub_high&&& &&&sum&&
sum = sum2;
sub_low = low2;
sub_high = high2;
cout&&sub_low&&& &&&sub_high&&& &&&sum&&
void main()
int A[] = {13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7};
int& sub_low =
int& sub_high =
cout&&max_subarray(A, 0, 15, sub_low, sub_high)&&
cout&&sub_low&&
cout&&sub_high&&
错在25-32行。
一、不得利用本站危害国家安全、泄露国家秘密，不得侵犯国家社会集体的和公民的合法权益，不得利用本站制作、复制和传播不法有害信息！
二、互相尊重，对自己的言论和行为负责。
本文标题：
本页链接：