问题描述:
给定一个整数数组a[0~n],求数组a的子数组,使其元素和为最大。
问题分析:
方法一:可以用普通的方法枚举所有的子数组,然后求出最大的子数组和,时间复杂度为O(n*n)。
方法二:问题描述符合动态规划最优子结构的要求。
设b[i]表示以a[i]结尾 的子数组的最大子段和,即:
b[i]=max{sum(a[j~k])},其中0<=j<=i,j<=k<=i。
因此对于数组a[0~n]的最大字段和为max{b[i]},其中0<=i<n。
在计算b[i]时,可以考虑以下三种情况:
1,b[i] = b[i-1]+a[i],当b[i-1]>0时,这时候的b[i]中包含a[i]。
2,b[i] = a[i],当b[i-1]<=0,这时候以a[i]重新作为b[i]的起点。
3,b[i]不包含a[i]的情况,这种情况在计算b[i]之前已经计算处结果,保存在b[0~i-1]中。最后计算max{b[i]}时会考虑到。
b[i] = max{ b[i-1]+a[i],a[i]}。
而数组a[0~n]则为max{b[i]}。
在实现时,可以省略数组b[i]。实现如下:
view plaincopy to clipboardprint?
1 #include <iostream>
2 using namespace std;
3 #define N 10
4 int max_sub_array(int &s,int &e,int * a)
5 {
6 int i=0;
7 int j =0;
8 int b,start,end;
9 int sum = 0;
10 sum = b = a[0];
11 s = e = start = end = 0;//s和e是整个数组a[0~n]的最大子段的起末位置。start和end是数组a[0~i]的起末位置。
12 for(i = 1;i<N;i++)
13 {
14 if(b>0)
15 {
16 b = b + a[i];
17 end = i;
18 }
19 else
20 {
21 b = a[i];
22 start = end = i;
23 }
24 if(sum<b)
25 {
26 sum = b;
27 s = start;
28 e = end;
29 }
30 }
31 return sum;
32 }
33 int main()
34 {
35 int a[N]={31,-41,59,26,-53,58,97,-93,-23,84};
36 int start,end;
37 int sum = max_sub_array(start,end,a);
38 cout << sum << " "<<start<< " "<<end<< endl;
39 }
1 #include <iostream>
2 using namespace std;
3 #define N 10
4 int max_sub_array(int &s,int &e,int * a)
5 {
6 int i=0;
7 int j =0;
8 int b,start,end;
9 int sum = 0;
10 sum = b = a[0];
11 s = e = start = end = 0;//s和e是整个数组a[0~n]的最大子段的起末位置。start和end是数组a[0~i]的起末位置。
12 for(i = 1;i<N;i++)
13 {
14 if(b>0)
15 {
16 b = b + a[i];
17 end = i;
18 }
19 else
20 {
21 b = a[i];
22 start = end = i;
23 }
24 if(sum<b)
25 {
26 sum = b;
27 s = start;
28 e = end;
29 }
30 }
31 return sum;
32 }
33 int main()
34 {
35 int a[N]={31,-41,59,26,-53,58,97,-93,-23,84};
36 int start,end;
37 int sum = max_sub_array(start,end,a);
38 cout << sum << " "<<start<< " "<<end<< endl;
39 }
本文来自CSDN博客,转载请标明出处:http://blog.csdn.net/clearriver/archive/2009/05/29/4224154.aspx
分享到:
相关推荐
C语言笔记——数组
用两个数组分别模拟 A->B 和B->A间通讯的信道。A、B两主机各自拥有独立线程。线程move用来模拟信道中信号的移动。线程show用于打印信道。其中线程move和show detach()后作为子线程在后台独立运行。
本代码主要利用MATLAB工具实现MATLAB——数组除法,简单明了,易于理解
数据结构(清华大学版)——数组和广义表
本文是C#学习书籍中的第六章节——数组。
java基础——数组及其应用(csdn)————程序
一個關於C语言——数组与指针的基本教程,簡單而實用
班级成绩管理——数组实现 统计班级每位学生的总评成绩,并根据总评成绩进行升序排序。整个文件夹,哈哈哈
c语言课程设计报告通讯录——数组
数据结构——数组及广义表.cpp
动力节点老杜Java基础入门学习教程分享——数组
第10章成绩统计——数组与字符串.ppt
3.编程实现:首先任意输入一个大于2且小于10的整数n,再输入一个由n决定的二维整型数组(n n),形成n n阶矩阵,将矩阵中最大元素所在的行和最小元素所在的行对调后,再输出该矩阵(注意:数组不允许动态定义)。...
VB常用算法——数组元素插入与删除[借鉴].pdf
零点起飞学Visual Basic之数据块——数组PPT学习教案.pptx
Swift从入门到精通视频教程下载第6章 Swift集合类型——数组和字典.zip
C++数据结构——链表,适合初学者,使用数组模拟链表。