文档章节

最大子数组的线性时间的算法

o
 osc_gu9d45li
发布于 2019/04/09 14:33
字数 1712
阅读 0
收藏 0
c++

行业解决方案、产品招募中!想赚钱就来传!>>>

 

问题来源:

 

这是真的牛批,没有答案,

 

这是:MaxSubLinear.h头文件:定义了一个类,用于求给定数组的最大子数组,成员变量和成员函数的说明如下:

成员变量:

  begin_index:最大子数组的起始索引;

  end_index:最大子数组的终止索引;

成员函数:

  maxSubArray:给定一个数组和其长度,返回最大子数组的和,参数返回起始索引和终止索引;

  linearMaxSubArray:上面函数的改进版本,100%线性时间;

  getBeginIndex和getEndIndex用于获取起始索引和终止索引;

 

#pragma once
class MaxSubLinear
{
public:
    MaxSubLinear();
    ~MaxSubLinear();
    static int maxSubArray(int* arr, int length, int& begin_index = begin_index, int& end_index = end_index);
    static int linearMaxSubArray(int* arr, int length, int& begin_index = begin_index, int& end_index = end_index);
    static int getBeginIndex() { return begin_index; }
    static int getEndIndex() { return end_index; }
private:
    static int begin_index;
    static int end_index;
};

现在需要根据题目的提示,实现最大子数组的函数:

  由题目,假设我们已知 A[1...j] 的最大子数组,设该最大子数组为:max_sub_array,接下来要求 A[1... j + 1]的最大子数组,那么A[1...j+1]的最大子数组不外乎两种情况:

    1.A[1... j+1]的最大子数组还是原来A[1...j]的最大子数组max_sub_array;

    2.A[1...j+1]的最大子数组是A[i ... j+1],其中1 <= i <=j+1;

  算法的核心就是如何从A[1..j]的最大子数组求出A[1..j+1]的最大子数组;

按照上面的分析,自然而然的可以想到如下的算法:

  INT_MIN 是 limits.h 中定义的一个常量,表示最小的int值,

int MaxSubLinear::maxSubArray(int* arr, int length, int& begin_index, int& end_index)
{
	int max_sub_sum = INT_MIN;
	int temp_sum = 0;
	for (int i = 0; i < length; i++) {
		for (int j = i; j >= 0; j--) {
			temp_sum += arr[j];
			if (temp_sum > max_sub_sum) {
				max_sub_sum = temp_sum;
				begin_index = j;
				end_index = i;
			}
		}
		temp_sum = 0;
	}
	return max_sub_sum;
}

  该算法基于如下思想:要从A[1...j]扩展到A[1...j+1],

    1.先求出A[1...j+1]包含j+1的子数组的最大值,记为temp_sum;

    2.将temp_sum和A[1...j]的最大子数组max_sub_sum进行比较,取其中的较大者为A[1...j+1]的最大子数组

  这个算法很好理解,上面内层的for循环就是求A[1...j+1]的包含j+1索引的最大子数组的过程;

  但遗憾的是这个算法并不是线性时间复杂度的,算法时间复杂度分析如下

    i = 0,内层循环1次

    i=1,内层循环2次

    ...

    i=length - 1,内层循环length次

  很明显,这是一个等差数列求和公式

  所以还是一个 复杂度的算法.

  当然该算法还可以优化:当arr[i] 为负数时,可以直接判断A[1...j+1]的最大子数组还是原来的A[1...j]的最大子数组,优化后的代码如下:

  

int MaxSubLinear::maxSubArray(int* arr, int length, int& begin_index, int& end_index)
{
    int max_sub_sum = INT_MIN;
    int temp_sum = 0;
    for (int i = 0; i < length; i++) {
        if (arr[i] < 0) {
            continue;
        }
        for (int j = i; j >= 0; j--) {
            temp_sum += arr[j];
            if (temp_sum > max_sub_sum) {
                max_sub_sum = temp_sum;
                begin_index = j;
                end_index = i;
            }
        }
        temp_sum = 0;
    }
    return max_sub_sum;
}

可以看到在内层循环开始前,先判断当前元素的正负,如果为负,可以断定,新的最大子数组还是原来的,直接开始下轮循环.但是,这种优化依然不能改变双重循环的事实,算法依然是 的.

正如牛顿说的,为什么他看的比别人远,因为他站在巨人的肩膀上,为达到真理所做的任何努力都不会白费的,当实现上述算法的时候,我们离线性时间复杂度仅一步之遥了.

分析下上述算法的内层循环,内层循环的功能是求A[1...j+1]的包含j+1索引的最大子数组,只要能够不使用循环求出A[1...j+1]的包含j+1索引的最大子数组就能实现线性时间复杂度,

 

  就像保存A[1...j]的最大子数组一样,我们可以添加一个变量用于保存A[1...j]的包含j索引的最大子数组;

  这样我们就能通过常数步骤实现包含最右边界的最大子数组的扩展.基于这种思想,线性时间复杂度算法如下:

 1 int MaxSubLinear::linearMaxSubArray(int* arr, int length, int& begin_index, int& end_index)
 2 {
 3     int max_sub_sum = INT_MIN;
 4     begin_index = end_index = -1;
 5 
 6     int max_sub_include_right = INT_MIN;//包含最有边元素的最大子数组
 7     int maybe_begin_index = -1;
 8     int maybe_end_index = -1;
 9 
10     for (int i = 0; i < length; i++) {
11         //先求出新的包含最右元素的新的最大子数组
12         if (max_sub_include_right+arr[i] > arr[i]) {
13             max_sub_include_right += arr[i];
14             maybe_end_index = i;
15         }
16         else {
17             max_sub_include_right = arr[i];
18             maybe_begin_index = i;
19         }
20         //取 包含最右元素的子数组 和 以前的最大子数组 中的最大者
21         if (max_sub_sum < max_sub_include_right) {
22             max_sub_sum = max_sub_include_right;
23             end_index = maybe_end_index;
24             begin_index = maybe_begin_index;
25         }
26     }
27     return max_sub_sum;
28 }

变量max_sub_include_right保存了包含目前最右索引的最大子数组的和,
maybe_begin_index和maybe_end_index分别是其左边界和右边界索引;

当需要向右扩展max_sub_include_right的时候,通过和新的最右边界arr[i] 相加再和max_sub_include_right比较来重新给表示包含有边界的三个变量max_sub_include_right,maybe_begin_index和maybe_end_index赋值;

最后再将包含右边界的最大子数组和原来的最大子数组比较来获得新的最大子数组.

MaxSubLinear.cpp的完整实现如下:

 1 #include "MaxSubLinear.h"
 2 #include "limits.h"
 3 
 4 
 5 MaxSubLinear::MaxSubLinear()
 6 {
 7 }
 8 
 9 
10 MaxSubLinear::~MaxSubLinear()
11 {
12 }
13 
14 //静态成员变量在类外面必须初始化
15 int MaxSubLinear::begin_index = 0;
16 int MaxSubLinear::end_index = 0;
17 
18 int MaxSubLinear::maxSubArray(int* arr, int length, int& begin_index, int& end_index)
19 {
20     int max_sub_sum = INT_MIN;
21     int temp_sum = 0;
22     for (int i = 0; i < length; i++) {
23         if (arr[i] < 0) {
24             continue;
25         }
26         for (int j = i; j >= 0; j--) {
27             temp_sum += arr[j];
28             if (temp_sum > max_sub_sum) {
29                 max_sub_sum = temp_sum;
30                 begin_index = j;
31                 end_index = i;
32             }
33         }
34         temp_sum = 0;
35     }
36     return max_sub_sum;
37 }
38 
39 int MaxSubLinear::linearMaxSubArray(int* arr, int length, int& begin_index, int& end_index)
40 {
41     int max_sub_sum = INT_MIN;
42     begin_index = end_index = -1;
43 
44     int max_sub_include_right = INT_MIN;//包含最有边元素的最大子数组
45     int maybe_begin_index = -1;
46     int maybe_end_index = -1;
47 
48     for (int i = 0; i < length; i++) {
49         //先求出新的包含最右元素的新的最大子数组
50         if (max_sub_include_right+arr[i] > arr[i]) {
51             max_sub_include_right += arr[i];
52             maybe_end_index = i;
53         }
54         else {
55             max_sub_include_right = arr[i];
56             maybe_begin_index = i;
57         }
58         //取 包含最右元素的子数组 和 以前的最大子数组 中的最大者
59         if (max_sub_sum < max_sub_include_right) {
60             max_sub_sum = max_sub_include_right;
61             end_index = maybe_end_index;
62             begin_index = maybe_begin_index;
63         }
64     }
65     return max_sub_sum;
66 }

对算法的测试代码如下:

int main()
{
    //                                    18,20,-7,12
    //             0  1  2  3  4   5   6  7  8  9  10  11  12 13 14 15
    int a[] = { 13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7 };
    int length = sizeof(a) / sizeof(a[0]);
    int begin_index = 0, end_index = 0, max_sum = 0;
    max_sum = MaxSubLinear::linearMaxSubArray(a, length);
    cout << "最大子数组从:" << MaxSubLinear::getBeginIndex() << "" << MaxSubLinear::getEndIndex() << " 最大子数组和是: " << max_sum << endl;
}

运行结果如下:

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
【opencv】图形的绘制

1.矩形图像的绘制: 原函数:void cvRectangle(CvArr* img, CvPoint pt1, CvPoint pt2, CvScalar color, int thickness=1, int line_type=8,int shift=0) img就是需要绘制的图像 pt1 and pt......

其实我是兔子
2014/10/08
1.1K
1
实时分析系统--istatd

istatd是IMVU公司工程师开发的一款优秀的实时分析系统,能够有效地收集,存储和搜索各种分析指标,类似cacti,Graphite,Zabbix等系统。实际上,istatd修改了Graphite的存储后端,重新实现了...

匿名
2013/02/07
2.8K
1
硬实时操作系统--Raw OS

Raw-OS 起飞于2012年,Raw-OS志在制作中国人自己的最优秀硬实时操作系统。 Raw-OS 操作系统特性 内核最大关中断时间无限接近0us, s3c2440系统最大关中断时间实测0.8us。 支持idle任务级别的事...

jorya_txj
2013/03/19
6.1K
1
C++科学计算库--O2scl

一个面向对象的 C++科学计算库,可用于解方程,最小化,微分,积分,插值,优化,逼近,分析,拟合等。许多类可操作于通用的函数和向量类型。可用于O2scl在Linux,Mac和Windows(Cygwin的)平...

匿名
2012/10/29
4.7K
0
高效率的nio框架--nio java raptor

设计初衷是提供方便易用,且高效率的nio框架,一部分实现上参考了mina。还包括线程池,编解码,内存池等机制,以便于开发高性能tcp程序。 文档后续会慢慢的补上。 整体实现上尽量少的使用锁,...

齐楠
2012/12/12
3.3K
0

没有更多内容

加载失败,请刷新页面

加载更多

如何在SQL Server中将多行文本合并为单个文本字符串?

问题: Consider a database table holding names, with three rows: 考虑一个包含名称的数据库表,该表具有三行: PeterPaulMary Is there an easy way to turn this into a single str......

富含淀粉
32分钟前
9
0
在JavaScript中生成特定范围内的随机整数? - Generating random whole numbers in JavaScript in a specific range?

问题: 如何可以生成两个指定的变量之间的随机整数在JavaScript中,例如x = 4和y = 8将输出任何的4, 5, 6, 7, 8 ? 解决方案: 参考一: https://stackoom.com/question/6PRz/在JavaScript中...

fyin1314
今天
8
0
Vim清除最后一个搜索突出显示 - Vim clear last search highlighting

问题: Want to improve this post? 想要改善这篇文章吗? Provide detailed answers to this question, including citations and an explanation of why your answer is correct. 提供此问题......

技术盛宴
今天
23
0
马化腾每天刷 Leetcode?代码你打算写到几岁?

本文作者:o****0 前几天,一张未证真伪的截图流传,图中显示马化腾几乎每天都会在 Leetcode 上提交代码。 截图还贴出一个 Leetcode 账户地址。该地址的头像已从马化腾的照片换成腾讯 logo,...

百度开发者中心
前天
13
0
滴滴 3000+ Kylin Cube 背后的实践经验揭秘

本次分享主要有三个部分:Kylin 在滴滴的整体应用、架构的实践经验、滴滴全局字典最新版本的实现以及 Kylin 最新实时 OLAP 探索经验分享。 Kylin 在滴滴的应用&架构 Kylin 在滴滴的三类应用场...

浪尖聊大数据
昨天
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部