算法导论之求解最大子数组问题python代码实现

r囧r小猫 2023-07-04 12:51 5阅读 0赞

# 算法导论之最大子数组问题 #

## 使用分治策略求解 ##

基于python的源代码如下：

#求出跨越中点的最大子数组
    def FIND_MAX_CROSSING_SUBARRARY(list,low,mid,high):
    	left_max = -float("inf")
    	right_max = -float("inf")
    	left_sum = 0
    	right_sum = 0
    	left_index = mid
    	right_index = mid
    	for i in range(mid,low-1,-1):
    		left_sum=left_sum+list[i]
    		if left_sum>left_max:
    			left_max=left_sum
    			left_index=i
    	for j in range(mid+1,high+1):
    		right_sum=right_sum+list[j]
    		if right_sum>right_max:
    			right_max=right_sum
    			right_index=j
    	return (left_index,right_index,left_max+right_max)
    
    def FIND_MAXIMUM_SUBARRARY(list,low,high):
    	left_low,left_high,left_sum = 0,0,0
    	right_low,right_high,right_sum = 0,0,0
    	cross_low,cross_high,cross_sum = 0,0,0
    	if high == low:
    		return (low,high,list[low])
    	else:
    		mid = (low + high) // 2
    		(left_low,left_high,left_sum)=FIND_MAXIMUM_SUBARRARY(list,low,mid)
    		(right_low,right_high,right_sum)=FIND_MAXIMUM_SUBARRARY(list,mid+1,high)
    		(cross_low,cross_high,cross_sum)=FIND_MAX_CROSSING_SUBARRARY(list,low,mid,high)
    		if left_sum>=right_sum and left_sum>=cross_sum:
    			return (left_low,left_high,left_sum)
    		if right_sum>=left_sum and right_sum>=cross_sum:
    			return (right_low,right_high,right_sum)
    		else:
    			return (cross_low,cross_high,cross_sum)

发表评论取消回复

表情：

评论列表（有 0 条评论，5人围观）

还没有评论，来说两句吧...

相关阅读

相关最大和连续子数组问题解析与代码实现

最大和连续子数组问题是一个经典的算法问题，给定一个整数数组，我们需要找到一个连续子数组，使得该子数组的元素和最大。在本文中，我们将详细解析这个问题，并给出相应的代码实现。问

怼烎@/ 2024年02月27日 02:01/ 0 赞/ 60 阅读

相关实现最大子数组算法 Java

实现最大子数组算法 Java 最大子数组算法是一种在给定数组中寻找连续子数组，使其具有最大和的算法。它是解决一类常见问题的有效方法，例如股票交易中的最大利润、数组元素之和的最

短命女/ 2023年10月14日 19:53/ 0 赞/ 59 阅读

相关算法导论之求解最大子数组问题python代码实现

算法导论之最大子数组问题使用分治策略求解基于python的源代码如下：求出跨越中点的最大子数组 def FIND_MAX_CROSSING_

r囧r小猫/ 2023年07月04日 12:51/ 0 赞/ 6 阅读

相关算法导论之分治策略：最大子数组问题

我们先说一下分治策略的基本步骤：首先我们要递归的求解一个问题，在每层的递归中会分为一下三个过程：分解：将大问题划分为子问题，子问题形同大问题，只是规模更小。解决：递归的

逃离我推掉我的手/ 2022年08月21日 00:03/ 0 赞/ 257 阅读

相关求解最大子序列算法及比较

include <iostream> include <stdlib.h> include <time.h> include "../StopW

谁践踏了优雅/ 2022年08月02日 06:22/ 0 赞/ 198 阅读

相关最大子数组问题

最大子数组问题从一个数组中寻找一个子数组（最少一个元素），使子数组中元素之和最大（必定包含负数，不然最大子数组就是原数组本身）。暴力求解我们很容易的想到一个

曾经终败给现在/ 2022年06月07日 10:17/ 0 赞/ 219 阅读

相关【算法导论笔记】最大连续子序列和

分别采用两种方法实现： 1. 分而治之递归解法 2. 线性数学解法 1. 分而治之递归解法分为三种情况， 1. 最大子序列和完全在左子数组； 2. 最大子

柔光的暖阳◎/ 2022年05月08日 13:04/ 0 赞/ 236 阅读

相关算法导论之最大子数组问题

例如我们在求解下面的最大子数组时 <table style="width:500px;"> <tbody> <tr> <td>13</td> <td

╰半夏微凉°/ 2022年03月21日 13:50/ 0 赞/ 225 阅读

相关分治算法解决最大子数组问题

以下为股票波动价格变化表，要求求出哪一天买入哪一天卖出得到的利润最大。 ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text

梦里梦外;/ 2022年03月01日 01:40/ 0 赞/ 276 阅读

相关【算法导论】最大子数组——递归

1.描述：找出数组A的和最大的非空连续子数组，我们称这样的连续子数组为最大子数组。用分治策略来求解。　　a. 假设我们要求A的子数组A[low, high]的最...

你的名字/ 2021年03月28日 13:56/ 0 赞/ 540 阅读