一、 问题描述
给出一个一维数组,数组中的数有正有负,求该数组中连续元素之和最大值
二、暴力法
2.1 解题思路
在数组中选一个位置i为起始位置,选一个位置j为终止位置,在i和j中选一个位置k,计算i到k位置元素的和,遍历i、j、k。
2.2 Python 代码
代码没有考虑数据长度为0的情况,后面的代码也是。
def enumeration(data):
m = data[0]
for i in range(len(data)):
for j in range(i+1, len(data)+1):
temp = 0
for k in range(i, j):
temp += data[k]
if temp > m:
m = temp
return m
2.3 时间复杂度
因为要遍历i、j、k,所以时间复杂度为
三、分治法
暴力法是一种很直接的方法,直接循环进行遍历,但是这种方法在笔试时肯定不符合要求,因为时间复杂度太高。而分治法可以有效降低时间复杂度,其思想是将大问题拆分成若干个小问题,然后依次解决。
3.1 解题思路
将数组从中间分成两段,此时最大连续子数组要么落在左半段,要么落在右半段,要么横跨中间的分界点。因此,可以设计程序计算左半端最大和,计算右半段最大和,计算横跨分界点的最大和,然后找出三者的最大值,即为最大连续子数组和。
首先计算横跨分界点的最大和。当横跨中间的分界点时,子数组左半端一定是从分界点开始往左连续,并且和是最大的。右半段同理。因此可以令m1=分界点开始往左连续最大和,m2=分界点开始往右连续最大和,m3 = m1 + m2,m3即为横跨分界点的最大和。
然后计算左半端最大和。当然可以采用暴力法解决,但是显而易见,我们可以再次将左半端从中间分成两部分,然后下一步再从小左半端从中间分成两部分,一直循环下去,直到数组中只有一个元素为止。整个过程是一个递归的过程,计算右半段时同理。
3.2 Python代码
def divide_conquer(data):
start = 0
end = len(data)
if len(data) == 1: # 递归调用的结束
return data[0]
middle = int((end - start) / 2)
max1 = divide_conquer(data[start: middle]) # 对左边计算最大值
max2 = divide_conquer(data[middle: end]) # 对右边计算最大值
left_temp = 0 # 计算从中间开始往左连续最大值
left_max = data[middle - 1]
for i in range(1, middle+1):
left_temp += data[middle - i]
if left_temp > left_max:
left_max = left_temp
right_temp = 0 # 计算从中间开始往右连续最大值
right_max = data[middle]
for i in range(0, end-middle):
right_temp += data[middle + i]
if right_temp > right_max:
right_max = right_temp
max3 = left_max + right_max
return max(max1, max2, max3)
3.3 时间复杂度分析
代码中包含三个计算过程:两个递归和一次遍历数据(从中间到两边),因此假设一维数组长度为的话,时间复杂度可以表示为:
为计算方便,假设,则
因此分治法的时间复杂度为
四、推理法
4.1 解题思路
从前到后只遍历一遍数据,从第一个位置开始加和,用temp_sum表示。如果temp_sum小于0,则令temp_sum = 0,重新进行累加。因为temp_sum小于0时,会对后面的累加产生副作用。找最大连续子数组和的话 ,就是在上述遍历的过程中,保存temp_sum的最大值。
4.2 Python代码
def reasoning(data):
temp_max = 0
temp_sum = data[0]
for i in range(1, len(data)):
if temp_sum < 0:
temp_sum = 0
temp_sum1 = temp_sum + data[i]
temp = max(temp_sum, temp_sum1)
if temp > temp_max:
temp_max = temp
temp_sum = temp_sum1
return temp_max
4.3 时间复杂度分析
由于只遍历一遍数据,所以时间复杂度为
五、动态规划法
5.1 解题思路
计算第i位置之前的最大子数组和,遍历i,取其中的最大值。
5.2 Python代码
def dynamic_planning(data):
temp_max = data[0]
temp_sum = data[0]
for i in range(1, len(data)):
temp_sum = max(temp_sum+data[i], data[i])
if temp_sum > temp_max:
temp_max = temp_sum
return temp_max
5.3 时间复杂度分析
由于只遍历一遍数据,所以时间复杂度为
六、时间对比
随机产生500和50万个随机整数,测试结果如下:
1.png 2.png
网友评论