Z*****Z
发帖数: 723 | 1 Maximum Sum of Increasing Subsequence
Given an integer array, how will you find out the increasing subsequence whi
ch gives the largest sum. For example,
50,23,1,67,30 in this subsequence a few possible increasing subsequences are
1) 23,30
2) 23,67
2) 50,67
3) 1,67
4) 1,30
5) 67
6) 30
but50, 67 gives the maximum sum. How to find it?
用DP，O（N）空间，O（N2）时间，是最优么？能不能像LIS那样优化成O（NlgN）？ |
y**i
发帖数: 1112 | 2
whi
are
这个用DP怎么解？
这个用brute force直接做两层循环不也是O(N2)时间么，还不用额外空间
【在 Z*****Z 的大作中提到】
: Maximum Sum of Increasing Subsequence
: Given an integer array, how will you find out the increasing subsequence whi
: ch gives the largest sum. For example,
: 50,23,1,67,30 in this subsequence a few possible increasing subsequences are
: 1) 23,30
: 2) 23,67
: 2) 50,67
: 3) 1,67
: 4) 1,30
: 5) 67
|
b********h
发帖数: 119 | 3 subsequence不是subarray吧。bruteforce应该是2^n。
DP的做法跟max subsequence一样，定义S(i)为在i结束的max increaseing sequence，
则，
S(i) = max{S(j)+A[i], A[i]>A[j] && 0<=j
【在 y**i 的大作中提到】
:
: whi
: are
: 这个用DP怎么解？
: 这个用brute force直接做两层循环不也是O(N2)时间么，还不用额外空间
|
Z*****Z
发帖数: 723 | 4 对，sequence不一定连续
【在 b********h 的大作中提到】
: subsequence不是subarray吧。bruteforce应该是2^n。
: DP的做法跟max subsequence一样，定义S(i)为在i结束的max increaseing sequence，
: 则，
: S(i) = max{S(j)+A[i], A[i]>A[j] && 0<=j
|
y**i
发帖数: 1112 | 5 我想的就是这样的，两个循环，外层循环是当前检测的subsequence的起始点，内层循
环是终结点，用一个变量max记录目前为止最大的sum，用另一个变量index记录上一个
检测的increasing subsequence的终结点，如果当前的内循环变量所指的元素大于变量
index所指元素，那么就更新increasing subsequence的终结点并把其于max的和跟max
比较及更新max。对这应该是DP思想，因为记录了检测过的increasing sequence的最大
和，而不是把所以的increasing subsequence先全部找出来再求和比较，那样确实是2^
n。
不过这个DP应该不需要额外O(n)空间，因为我们只要记录最大就可以了对吧，没必要记录所有的sum
【在 b********h 的大作中提到】
: subsequence不是subarray吧。bruteforce应该是2^n。
: DP的做法跟max subsequence一样，定义S(i)为在i结束的max increaseing sequence，
: 则，
: S(i) = max{S(j)+A[i], A[i]>A[j] && 0<=j
|
Z*****Z
发帖数: 723 | 6 问题是如果内循环变量所指元素小于index所指元素应该如何做呢？
我想的就是这样的，两个循环，外层循环是当前检测的subsequence的起始点，内层循
环是终结点，用一个变量max记录目前为止最大的sum，用另一个变量index记录上一个
检测的increasing subsequence的终结点，如果当前的内循环变量所指的元素大于变量
index所指元素，那么就更新increasing subsequence的终结点并把其于max的和跟max
比较及更新max。对这应该是DP思想，因为记录了检测过的increasing sequence的最大
和，而不是把所以的increasing subsequence先全部找出来再求和比较，那样确实是2^
n。
不过这个DP应该不需要额外O(n)空间，因为我们只要记录最大就可以了对吧，没必要记
录所有的sum
【在 y**i 的大作中提到】
: 我想的就是这样的，两个循环，外层循环是当前检测的subsequence的起始点，内层循
: 环是终结点，用一个变量max记录目前为止最大的sum，用另一个变量index记录上一个
: 检测的increasing subsequence的终结点，如果当前的内循环变量所指的元素大于变量
: index所指元素，那么就更新increasing subsequence的终结点并把其于max的和跟max
: 比较及更新max。对这应该是DP思想，因为记录了检测过的increasing sequence的最大
: 和，而不是把所以的increasing subsequence先全部找出来再求和比较，那样确实是2^
: n。
: 不过这个DP应该不需要额外O(n)空间，因为我们只要记录最大就可以了对吧，没必要记录所有的sum
|
y**i
发帖数: 1112 | 7 我知道了，我想错了，是要记录下所有之前的sum，然后每次从之前的sum中找出最大的
再记录
max
2^
【在 Z*****Z 的大作中提到】
: 问题是如果内循环变量所指元素小于index所指元素应该如何做呢？
:
: 我想的就是这样的，两个循环，外层循环是当前检测的subsequence的起始点，内层循
: 环是终结点，用一个变量max记录目前为止最大的sum，用另一个变量index记录上一个
: 检测的increasing subsequence的终结点，如果当前的内循环变量所指的元素大于变量
: index所指元素，那么就更新increasing subsequence的终结点并把其于max的和跟max
: 比较及更新max。对这应该是DP思想，因为记录了检测过的increasing sequence的最大
: 和，而不是把所以的increasing subsequence先全部找出来再求和比较，那样确实是2^
: n。
: 不过这个DP应该不需要额外O(n)空间，因为我们只要记录最大就可以了对吧，没必要记
|
c********g
发帖数: 13 | 8 这个应该可以
#define nums 8
#include
using namespace std;
int main()
{
int max[10];
int pre[10];
int num[100]={50,23,1,67,30,40,45,49};
max[0]=num[0];
pre[0]=0;
for(int i=1;i
{
int temp=0;
max[i]=num[i];
pre[i]=i;
for(int j=0;j
{
if(num[i]>num[j])
{
if(max[j]>=temp)
{
temp=max[j];
|
r****o
发帖数: 1950 | 9 这个DP和找longest increasing subsequence差不多吧。
whi
are
【在 Z*****Z 的大作中提到】
: Maximum Sum of Increasing Subsequence
: Given an integer array, how will you find out the increasing subsequence whi
: ch gives the largest sum. For example,
: 50,23,1,67,30 in this subsequence a few possible increasing subsequences are
: 1) 23,30
: 2) 23,67
: 2) 50,67
: 3) 1,67
: 4) 1,30
: 5) 67
|
Z*****Z
发帖数: 723 | 10 对，基本DP解法是一样的，LIS能优化，这个能不？
【在 r****o 的大作中提到】
: 这个DP和找longest increasing subsequence差不多吧。
:
: whi
: are
|
|
|
c********g
发帖数: 13 | 11 我的教授说LIS能优化到O(NlgN),但他说的那段我没听懂，后来知道考试不考也就没细
想了。不过我猜这个也应该能优化到O(NlgN)
【在 Z*****Z 的大作中提到】
: 对，基本DP解法是一样的，LIS能优化，这个能不？
|
Z*****Z
发帖数: 723 | 12 想了一下，觉得玄。
LIS优化的巧妙之处在于sequence长度不会超过输入数组的长度，对每个increasing su
bsequence可以根据其长度记录那个最后的元素。
这里是和，貌似不太可能
【在 c********g 的大作中提到】
: 我的教授说LIS能优化到O(NlgN),但他说的那段我没听懂，后来知道考试不考也就没细
: 想了。不过我猜这个也应该能优化到O(NlgN)
|
y**i
发帖数: 1112 | 13 LIS的优化是维护一个当前最长递增子序列（下标），并把这个子序列里当前考察元素的前
一个元素下标保存下来，然后在考察下一个元素的时候用二分查找的方法去更新这个子
序列（更新过程中不能保证有序），同样记录子序列中当前元素的前一个元素下标。最
后用倒序的方法找出最长子序列。
如果用在求和上，就是看怎么把这个“最长”改成“最大和”。
【在 c********g 的大作中提到】
: 我的教授说LIS能优化到O(NlgN),但他说的那段我没听懂，后来知道考试不考也就没细
: 想了。不过我猜这个也应该能优化到O(NlgN)
|
r****o
发帖数: 1950 | 14 多谢，请问哪儿有关于这个LIS的优化的详细资料？
素的前
【在 y**i 的大作中提到】
: LIS的优化是维护一个当前最长递增子序列（下标），并把这个子序列里当前考察元素的前
: 一个元素下标保存下来，然后在考察下一个元素的时候用二分查找的方法去更新这个子
: 序列（更新过程中不能保证有序），同样记录子序列中当前元素的前一个元素下标。最
: 后用倒序的方法找出最长子序列。
: 如果用在求和上，就是看怎么把这个“最长”改成“最大和”。
|
y**i
发帖数: 1112 | 15 我就是在wiki上看到的一个external link，连代码都有。给你链接：
http://www.algorithmist.com/index.php/Longest_Increasing_Subsequence
【在 r****o 的大作中提到】
: 多谢，请问哪儿有关于这个LIS的优化的详细资料？
:
: 素的前
|
