问题描述:
有一串数字(可正可负的int,放在数组Num里),要求找到起始位置start和终止位置end,使得从start位置到end位置的所有数字之和最大,返回这个最大值max。
算法思想:使用动态规划。
设 f[x] 为以 a[x] 终止且包含 a[x] 的最大序列的和,有:
f[1] = a[1];
f[x+1] = f[x] > 0 ? f[x] + a[x+1] : a[x+1]
那么最大子序列的和就是 f[1] .. f[n] 中最大的一个。其算法的时间复杂度为O(n),代码实现如下:
void maxSubse(int[] a, int length) {
int start, resultBegin, resultEnd;
int max, resultMax;
int i;
start = resultBegin = resultEnd = 0;
max = resultMax = a[0];
for(i = 1; i < length; i++) {
if (max > 0) {
max += a[i];
}
else {
max = a[i];
start = i;
}
if (max > resultMax) {
resultMax = max;
resultStart = start;
resultEnd = i;
}
}
}
分享到:
相关推荐
最大连续子序列
把一个包含n个正整数的序列划分成m个连续的子序列,每个整数刚好属于一个序列。设第i个序列的各数之和是S(i)。要求:让所有的S(i)的最大值尽量小。例如:序列1,2,3,2,5,4划分成3个序列的最优方案为123|25|4,...
把一个包含n个正整数的序列划分成m个连续的子序列,每个整数刚好属于一个序列。设第i个序列的各数之和是S(i)。要求:让所有的S(i)的最大值尽量小。例如:序列1,2,3,2,5,4划分成3个序列的最优方案为123|25|4,...
在一个数组中找出连续元素的最大值,时间复杂度o(n),空间复杂度o(n)
提醒:此最大乘积连续子串与最大乘积子序列不同,请勿混淆,前者子串要求连续,后者子序列不要求连续。也就是说:最长公共子串(Longest CommonSubstring)和最长公共子序列(LongestCommon Subsequence,LCS)的...
给定由n整数(可能为负数)组成的序列 {a1,a2,…,an},求该序列形如ai+ai+1,…,+aj的子段和的最大值。当所有的整数均为负数时定义其最大子段和为0。 Input 输入包含多组测试数据。第一行为一个整数C,表示有C组...
问题:输入一个长度为n的整数序列,从中找出一段不超过M的连续子序列,使得整个序列的和最大。 采用c#实现:求最大子序列的值。
(注:这两天看《编程之美》,发现2.14节,求数组的子数组之和的最大值,跟这个题十分相似,但是没有要求求出开始喝结束的位置,只要求求出最大值,解题思路跟下面的代码相似,但只用了两个变量,没有用数组,做到...
给一个数组,返回它的最大连续子序列的和使用动态规划F(i):以array[i]为末尾元素的子数组的和的最大值,子数组的元素的相对位置不变res:所有子数组的和的
蛮力法、分治法和动态规划法设计最大子段和问题的算法,一、试分别利用蛮力法、分治法和动态规划法求解最大子段和问题,要求写出C/C++程序实现...程序运行结果要同时给出最大子段和的值以及由哪个子段取得该最大子段和。
把一个包含n个正整数的序列划分成m个连续的子序列,每个整数刚好属于一个序列。设第i个序列的各数之和是S(i)。要求:让所有的S(i)的最大值尽量小。例如:序列1,2,3,2,5,4划分成3个序列的最优方案为123|25|4,...
php实现正负数数组最大子序列,要求给出数组,该数组由正负数字组成,找出该数组中连续元素组成的子数组的最大值。这其实得算是个背包变种吧。 复制代码 代码如下:<?php$list = array(1,-3,-5,-7,8,9,-11,5); $...
本资源为山东科技大学计算机算法设计与分析的实验报告,分别用暴力...给定n个整数(可能为负整数)组成的序列a1,a2,…,an,求该序列连续的子序列和的最大值。 如果该子段的所有元素和是负整数时定义其最大子段和为0。
今天被小伙伴问到最长子串的东西,注意哦,它这里是要求连续的哦,和我之前的最长公共子序列有些不一样,但是捏,大同小异啦最长公共子序列 这次这位小伙伴问的是python的,那我就用python做一下吧(太久没写,真的...
最大子序列和问题(Maximum Subarray Sum Problem)是求解一个数组中连续子数组的和的最大值的问题。
把一个包含n个正整数的序列划分成m个连续的子序列,每个整数刚好属于一个序列。设第i个序列的各数之和是S(i)。要求:让所有的S(i)的最大值尽量小。例如:序列1,2,3,2,5,4划分成3个序列的最优方案为123|25|4,...
最长上升子序列问题可以这样定义:给定一个无序的整数数组,任务是找到该数组中一个最长的子序列,使得这个子序列中的元素从左到右是严格递增的...最后,我们遍历dp数组,找到其中的最大值,即为最长上升子序列的长度。
但是没有包含”连续子序列最大积值“这样的题目,并且”最长递增子序列“给出的解答不是最优的,这两个题目大家可以额外思考一下,面试中也很常见。 另外,面试过程中也会遇到很多与系统相关的知识性的题目,如流水...
leetcode中国数据结构和算法 ...找到最长的连续子序列 给定一个大小为 n 的数组和一个数字 k,找出出现次数超过“n/k”次的所有元素。 最多两次买卖股票的最大利润 判断一个数组是否是另一个数组的子集 找
翻转单词顺序列,反转链表,斐波那契数列,复杂链表的复制,构建乘积数组,和为s的连续整数序列,和为s的两个数字,滑动窗口的最大值,机器人的运动范围,剑指offer-python实现.docx,矩形覆盖,矩阵中的路径,连续子数组的最大...