前些天学车...真是相当累啊,比上课累,现在终于可以休息了...
重新看《算法导论》,不过这下可得认真看了,9个月不到就得去找工作了,与我同样的大三党们一样加油咯...
《算法导论》中引入这个问题是通过股票的购买与出售,将前一天的当天的股票差价重新表示出来,即转为了一个最大子数组的问题,具体内容我不多说,转的内容是:
13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7
找到这连续的16个数里面的连续和最大的子数组;
书中练习部分说用设计非递归的,线性时间的算法,我就YY为动态规划处理了;
从数组的左边界开始,从左至右处理,记录到目前为止已经处理过的最大子数组。若已知A[1..j]的最大子数组,基于如下性质将解扩展为A[1...j+1]的最大子数组:A[1...j+1]的最大子数组要么是A[1...j]的最大子数组,要么是某个子数组A[i...j+1](1<=i<=j+1)。在已知A[1...j]的最大子数组的情况下,可以在线性时间内找出形如A[i...j+1]的最大子数组;
思想上述都将出来了,只要将关键点写出即可:
如果前面若干和<0,则其对后面子数组相加无帮助,此时重置dp为array[i],并且记录的起始位置重新标记;
if(dp[i - 1] <= 0) //前面的<0,直接丢弃
{
dp[i] = array[i];
temp = i; //记录起始为止
}
否则,继续往后延伸;
dp[i] = array[i] + dp[i - 1]; //往后求和
最后判断最大子数组值就行,同时标记起始与结束位置:
if(dp[i] > MaxSumSub) //找到到i为止的最大子数组
{
MaxSumSub = dp[i]; //最大...
start = temp; //标记起始
end = i; //标记此时的结束位置
}
代码:
#include <iostream>
using namespace std;
int FindMaxSubarray(int array[], int length)
{
int start = 0, end = 0; //记录最大子数组的起始位置(在数组中的下标)
int MaxSumSub; //最大子数组的值
int* dp = new int[length]; //动态规划记录
dp[0] = array[0]; //初始为第一个数
MaxSumSub = dp[0]; //最大值初始为第一个数
int temp = 0; //
for(int i = 1; i < length; i++)
{
if(dp[i - 1] <= 0) //前面的<0,直接丢弃
{
dp[i] = array[i];
temp = i; //记录起始为止
}
else
dp[i] = array[i] + dp[i - 1]; //往后求和
if(dp[i] > MaxSumSub) //找到到i为止的最大子数组
{
MaxSumSub = dp[i]; //最大...
start = temp; //标记起始
end = i; //标记此时的结束位置
}
}
cout<<"最大子序列的下标:"<<start<<"->"<<end<<endl;
return MaxSumSub;
}
int main()
{
int a[] = {13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7};
//int a[] = {23, 4};
int length = sizeof(a) / sizeof(int);
cout<<FindMaxSubarray(a, length);
return 0;
}
最大子序列即为{18, 20, -7, 12};
上述dp即为动态记录寻找最大子数组的过程,大家也可以进行输出看一下;
欢迎大家指点,o(∩_∩)o
分享到:
相关推荐
最大子数组和问题可以通过动态规划算法来解决,时间复杂度为O(n),其中n为数组长度。 最大子数组和的具体步骤如下: 1. 定义两个变量max_sum和cur_sum,分别表示当前已经遍历到的最大子数组和和当前子数组和。 2....
分治策略求解最大子数组问题
53. 最大子数组和 给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。 子数组 是数组中的一个连续部分。 示例 1: 输入:nums = [-2,1,-3,4,-1,2,1,-5,4] 输出...
(9条消息) 【中国大学MOOC】算法设计与分析-分而治之篇一-最大子数组1-Java_t949500898的博客-CSDN博客.html
C语言求最大子数组的算法探析.pdf
C语言求最大子数组的算法探析.pdf
53. 最大子序和 动态规划def maxSubArray(self, nums: List[int]) -> int:# 第一个元素 前面没有子数组# 状态转
分治法应用分治法求最大子数组以及其对应的下标分治法求最大子数组以及其对应的下标
LeetCode_0053_最大子数组和(简单, 2022-01)问题简述给定整数数组 nums ,返回连续子数组的最大和(子数组最少包含一个元素)。详细描述给
给定一个n个元素的数组,数组元素全部为整数,负数,正数和0均有可能存在,设设计一个算法,找出连续的几个数组元素相乘积最大
用动态规划法 蛮力法 分治法实现最大子数组和
分而治之的思想解决求一个数组的最大子集,有效的降低了时间复杂度,值得学习。
遍历 分治 动态规划
给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。示例 2:输出:1示例 3:输出:23提示:进阶:如果
求元素组合成连续子数组之和最大的子数组,要求时间复杂度为O(n)
动态规划算法:最大子序列问题
给定一个二维数组,由其中若干邻近元素构成的矩形称为子数组,请编写程序计算所有子数组元素之和的最大值。 【输入数据】第一行是一个整数N,表示二维数组的大小为N*N。接下来的N*N个数被空格和换行符隔开,表示按照...
最有用的Leetcode问题 Python解决方案,并附有说明 大批 -两个和-https: -买卖股票的最佳时间-https: -包含重复-https: -阵列除自身以外的产品-https: -最大子数组-https: -最大产品子数组-https: - -...
前75个最有用的Leetcode问题 Python解决方案,带注释 大批 -两个和-https: -买卖股票的最佳时间-https: -包含重复-https: -阵列除自身以外的产品-https: -最大子数组-https: -最大产品子数组-https: - ...
使用动态规划完成最大子数组问题 @ 2018-11-25 02:39 - 堆排序 @ 2018-12-03 16:25 - 快速排序 @ 2018-12-07 15:15 - 数据结构 栈 @ 2018-12-07 15:31 - 数据结构 队列 @ 2018-12-07 16:59 - 数据结构 双端队列 @ ...