原文:
最大和递增子序列问题是求给定序列的最大和子序列，使得子序列的所有元素按递增顺序排序。
示例:
input: [1, 101, 2, 3, 100, 4, 5]
output: [1, 2, 3, 100]
input: [3, 4, 5, 10]
output: [3, 4, 5, 10]
input: [10, 5, 4, 3]
output: [10]
input: [3, 2, 6, 4, 5, 1]
output: [3, 4, 5]
在帖子中，我们已经讨论了最大和增子序列问题。然而，这篇文章只涵盖了与求增子序列的最大和有关的代码，而没有涉及子序列的构造。在这篇文章中，我们将讨论如何构造最大和增子序列本身。
让 arr[0..n-1]是输入数组。我们定义向量 l，使得 l[i]本身是存储 arr[0]的最大和增子序列的向量..那以逮捕结束。因此，对于索引 i，l[i]可以递归地写成
l[0] = {arr[0]}
l[i] = {maxsum(l[j])} arr[i] where j < i and arr[j] < arr[i]
= arr[i], if there is no j such that arr[j] < arr[i]
例如，对于数组[3，2，6，4，5，1]，
l[0]: 3
l[1]: 2
l[2]: 3 6
l[3]: 3 4
l[4]: 3 4 5
l[5]: 1
以下是上述想法的实现–
c
/* dynamic programming solution to construct
maximum sum increasing subsequence */
#include
#include
using namespace std;
// utility function to calculate sum of all
// vector elements
int findsum(vector arr)
{
int sum = 0;
for (int i : arr)
sum = i;
return sum;
}
// function to construct maximum sum increasing
// subsequence
void printmaxsumis(int arr[], int n)
{
// l[i] - the maximum sum increasing
// subsequence that ends with arr[i]
vector > l(n);
// l[0] is equal to arr[0]
l[0].push_back(arr[0]);
// start from index 1
for (int i = 1; i < n; i ) {
// for every j less than i
for (int j = 0; j < i; j ) {
/* l[i] = {maxsum(l[j])} arr[i]
where j < i and arr[j] < arr[i] */
if ((arr[i] > arr[j])
&& (findsum(l[i]) < findsum(l[j])))
l[i] = l[j];
}
// l[i] ends with arr[i]
l[i].push_back(arr[i]);
// l[i] now stores maximum sum increasing
// subsequence of arr[0..i] that ends with
// arr[i]
}
vector res = l[0];
// find max
for (vector x : l)
if (findsum(x) > findsum(res))
res = x;
// max will contain result
for (int i : res)
cout << i << " ";
cout << endl;
}
// driver code
int main()
{
int arr[] = { 3, 2, 6, 4, 5, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
// construct and print max sum is of arr
printmaxsumis(arr, n);
return 0;
}
java 语言(一种计算机语言，尤用于创建网站)
/* dynamic programming solution to construct
maximum sum increasing subsequence */
import java.util.*;
class gfg {
// utility function to calculate sum of all
// vector elements
static int findsum(vector arr)
{
int sum = 0;
for (int i : arr)
sum = i;
return sum;
}
// function to construct maximum sum increasing
// subsequence
static void printmaxsumis(int[] arr, int n)
{
// l[i] - the maximum sum increasing
// subsequence that ends with arr[i]
@suppresswarnings("unchecked")
vector[] l = new vector[n];
for (int i = 0; i < n; i )
l[i] = new vector<>();
// l[0] is equal to arr[0]
l[0].add(arr[0]);
// start from index 1
for (int i = 1; i < n; i ) {
// for every j less than i
for (int j = 0; j < i; j ) {
/*
* l[i] = {maxsum(l[j])} arr[i]
where j < i and arr[j] < arr[i]
*/
if ((arr[i] > arr[j])
&& (findsum(l[i]) < findsum(l[j]))) {
for (int k : l[j])
if (!l[i].contains(k))
l[i].add(k);
}
}
// l[i] ends with arr[i]
l[i].add(arr[i]);
// l[i] now stores maximum sum increasing
// subsequence of arr[0..i] that ends with
// arr[i]
}
vector res = new vector<>(l[0]);
// res = l[0];
// find max
for (vector x : l)
if (findsum(x) > findsum(res))
res = x;
// max will contain result
for (int i : res)
system.out.print(i " ");
system.out.println();
}
// driver code
public static void main(string[] args)
{
int[] arr = { 3, 2, 6, 4, 5, 1 };
int n = arr.length;
// construct and print max sum is of arr
printmaxsumis(arr, n);
}
}
// this code is contributed by
// sanjeev2552
python 3
# dynamic programming solution to construct
# maximum sum increasing subsequence */
# utility function to calculate sum of all
# vector elements
def findsum(arr):
summ = 0
for i in arr:
summ = i
return summ
# function to construct maximum sum increasing
# subsequence
def printmaxsumis(arr, n):
# l[i] - the maximum sum increasing
# subsequence that ends with arr[i]
l = [[] for i in range(n)]
# l[0] is equal to arr[0]
l[0].append(arr[0])
# start from index 1
for i in range(1, n):
# for every j less than i
for j in range(i):
# l[i] = {maxsum(l[j])} arr[i]
# where j < i and arr[j] < arr[i]
if ((arr[i] > arr[j]) and
(findsum(l[i]) < findsum(l[j]))):
for e in l[j]:
if e not in l[i]:
l[i].append(e)
# l[i] ends with arr[i]
l[i].append(arr[i])
# l[i] now stores maximum sum increasing
# subsequence of arr[0..i] that ends with
# arr[i]
res = l[0]
# find max
for x in l:
if (findsum(x) > findsum(res)):
res = x
# max will contain result
for i in res:
print(i, end=" ")
# driver code
arr = [3, 2, 6, 4, 5, 1]
n = len(arr)
# construct and prmax sum is of arr
printmaxsumis(arr, n)
# this code is contributed by mohit kumar
c
/* dynamic programming solution to construct
maximum sum increasing subsequence */
using system;
using system.collections.generic;
class gfg {
// utility function to calculate sum of all
// vector elements
static int findsum(list arr)
{
int sum = 0;
foreach(int i in arr) sum = i;
return sum;
}
// function to construct maximum sum increasing
// subsequence
static void printmaxsumis(int[] arr, int n)
{
// l[i] - the maximum sum increasing
// subsequence that ends with arr[i]
list[] l = new list[ n ];
for (int i = 0; i < n; i )
l[i] = new list();
// l[0] is equal to arr[0]
l[0].add(arr[0]);
// start from index 1
for (int i = 1; i < n; i ) {
// for every j less than i
for (int j = 0; j < i; j ) {
/*
* l[i] = {maxsum(l[j])} arr[i]
where j < i and arr[j] < arr[i]
*/
if ((arr[i] > arr[j])
&& (findsum(l[i]) < findsum(l[j]))) {
foreach(int k in
l[j]) if (!l[i].contains(k))
l[i]
.add(k);
}
}
// l[i] ends with arr[i]
l[i].add(arr[i]);
// l[i] now stores maximum sum increasing
// subsequence of arr[0..i] that ends with
// arr[i]
}
list res = new list(l[0]);
// res = l[0];
// find max
foreach(list x in l) if (findsum(x)
> findsum(res)) res
= x;
// max will contain result
foreach(int i in res) console.write(i " ");
console.writeline();
}
// driver code
public static void main(string[] args)
{
int[] arr = { 3, 2, 6, 4, 5, 1 };
int n = arr.length;
// construct and print max sum is of arr
printmaxsumis(arr, n);
}
}
// this code is contributed by princiraj1992
java 描述语言
output
3 4 5
我们可以通过移除 findsum()函数来优化上面的 dp pg电子试玩链接的解决方案。相反，我们可以维护另一个向量/数组来存储以 arr[i]结束的最大和递增子序列的和。实现可以在这里看到。
以上动态规划解的时间复杂度为 o(n 2 )。 程序使用的辅助空间为 o(n 2 )。
方法 2: ( 使用使用 o(n)空间的动态规划
上述方法涵盖了如何在 o(n 2 )时间和 o(n 2 空间中构造最大和增子序列。在这种方法中，我们将优化空间复杂度，并在 o(n)2时间和 o(n)空间中构造最大和增子序列。
- 让 arr[0..n-1]是输入数组。
- 我们定义一个向量对 l，使得 l[i]首先存储 arr[0]的最大和增加子序列..以逮捕和拘留结束。第二个存储用于生成总和的前一个元素的索引。
- 由于第一个元素没有任何前一个元素，因此它的索引应该是 l[0]中的-1。
例如，
array = [3, 2, 6, 4, 5, 1]
l[0]: {3, -1}
l[1]: {2, 1}
l[2]: {9, 0}
l[3]: {7, 0}
l[4]: {12, 3}
l[5]: {1, 5}
如上所述，最大和递增子序列的值是 12。为了构建实际的子序列，我们将使用存储在 l[i]中的索引。其次，构建子序列的步骤如下所示:
- 在向量结果中，存储找到最大和递增子序列的元素的值(即 currindex = 4)。所以在结果向量中，我们将添加 arr[currindex]。
- 将 currindex 更新为 l[currindex]。其次，重复步骤 1，直到 currindex 不为-1 或不发生变化(即 currindex = = previousindex)。
- 以相反的顺序显示结果向量的元素。
下面是上述想法的实现:
c 14
/* dynamic programming solution to construct
maximum sum increasing subsequence */
#include
using namespace std;
// function to construct and print the maximum sum
// increasing subsequence
void constructmaxsumis(vector arr, int n)
{
// l[i] stores the value of maximum sum increasing
// subsequence that ends with arr[i] and the index of
// previous element used to construct the subsequence
vector > l(n);
int index = 0;
for (int i : arr) {
l[index] = { i, index };
index ;
}
// set l[0].second equal to -1
l[0].second = -1;
// start from index 1
for (int i = 1; i < n; i ) {
// for every j less than i
for (int j = 0; j < i; j ) {
if (arr[i] > arr[j]
and l[i].first < arr[i] l[j].first) {
l[i].first = arr[i] l[j].first;
l[i].second = j;
}
}
}
int maxi = int_min, currindex, track = 0;
for (auto p : l) {
if (p.first > maxi) {
maxi = p.first;
currindex = track;
}
track ;
}
// stores the final subsequence
vector result;
// index of previous element
// used to construct the subsequence
int prevoiusindex;
while (currindex >= 0) {
result.push_back(arr[currindex]);
prevoiusindex = l[currindex].second;
if (currindex == prevoiusindex)
break;
currindex = prevoiusindex;
}
for (int i = result.size() - 1; i >= 0; i--)
cout << result[i] << " ";
}
// driver code
int main()
{
vector arr = { 1, 101, 2, 3, 100, 4, 5 };
int n = arr.size();
// function call
constructmaxsumis(arr, n);
return 0;
}
java 语言(一种计算机语言，尤用于创建网站)
// dynamic programming solution to construct
// maximum sum increasing subsequence
import java.util.*;
import java.awt.point;
class gfg{
// function to construct and print the maximum sum
// increasing subsequence
static void constructmaxsumis(list arr, int n)
{
// l.get(i) stores the value of maximum sum increasing
// subsequence that ends with arr.get(i) and the index of
// previous element used to construct the subsequence
list l = new arraylist();
int index = 0;
for(int i : arr)
{
l.add(new point(i, index));
index ;
}
// set l[0].second equal to -1
l.set(0, new point(l.get(0).x, -1));
// start from index 1
for(int i = 1; i < n; i )
{
// for every j less than i
for(int j = 0; j < i; j )
{
if (arr.get(i) > arr.get(j) &&
l.get(i).x < arr.get(i)
l.get(j).x)
{
l.set(i, new point(arr.get(i)
l.get(j).x, j));
}
}
}
int maxi = -100000000, currindex = 0, track = 0;
for(point p : l)
{
if (p.x > maxi)
{
maxi = p.x;
currindex = track;
}
track ;
}
// stores the final subsequence
list result = new arraylist();
// index of previous element
// used to construct the subsequence
int prevoiusindex;
while (currindex >= 0)
{
result.add(arr.get(currindex));
prevoiusindex = l.get(currindex).y;
if (currindex == prevoiusindex)
break;
currindex = prevoiusindex;
}
for(int i = result.size() - 1; i >= 0; i--)
system.out.print(result.get(i) " ");
}
// driver code
public static void main(string []s)
{
list arr = new arraylist();
arr.add(1);
arr.add(101);
arr.add(2);
arr.add(3);
arr.add(100);
arr.add(4);
arr.add(5);
int n = arr.size();
// function call
constructmaxsumis(arr, n);
}
}
// this code is contributed by rutvik_56
python 3
# dynamic programming solution to construct
# maximum sum increasing subsequence
import sys
# function to construct and print the maximum sum
# increasing subsequence
def constructmaxsumis(arr, n) :
# l[i] stores the value of maximum sum increasing
# subsequence that ends with arr[i] and the index of
# previous element used to construct the subsequence
l = []
index = 0
for i in arr :
l.append([i, index])
index = 1
# set l[0].second equal to -1
l[0][1] = -1
# start from index 1
for i in range(1, n) :
# for every j less than i
for j in range(i) :
if (arr[i] > arr[j] and l[i][0] < arr[i] l[j][0]) :
l[i][0] = arr[i] l[j][0]
l[i][1] = j
maxi, currindex, track = -sys.maxsize, 0, 0
for p in l :
if (p[0] > maxi) :
maxi = p[0]
currindex = track
track = 1
# stores the final subsequence
result = []
while (currindex >= 0) :
result.append(arr[currindex])
prevoiusindex = l[currindex][1]
if (currindex == prevoiusindex) :
break
currindex = prevoiusindex
for i in range(len(result) - 1, -1, -1) :
print(result[i] , end = " ")
arr = [ 1, 101, 2, 3, 100, 4, 5 ]
n = len(arr)
# function call
constructmaxsumis(arr, n)
# this code is contributed by divyeshrabadiya07
c
/* dynamic programming solution to construct
maximum sum increasing subsequence */
using system;
using system.collections.generic;
class gfg
{
// function to construct and print the maximum sum
// increasing subsequence
static void constructmaxsumis(list arr, int n)
{
// l[i] stores the value of maximum sum increasing
// subsequence that ends with arr[i] and the index of
// previous element used to construct the subsequence
list> l = new list>();
int index = 0;
foreach(int i in arr) {
l.add(new tuple(i, index));
index ;
}
// set l[0].second equal to -1
l[0] = new tuple(l[0].item1, -1);
// start from index 1
for (int i = 1; i < n; i )
{
// for every j less than i
for (int j = 0; j < i; j )
{
if (arr[i] > arr[j] &&
l[i].item1 < arr[i]
l[j].item1)
{
l[i] = new tuple(arr[i] l[j].item1, j);
}
}
}
int maxi = int32.minvalue,
currindex = 0, track = 0;
foreach(tuple p in l)
{
if (p.item1 > maxi)
{
maxi = p.item1;
currindex = track;
}
track ;
}
// stores the final subsequence
list result = new list();
// index of previous element
// used to construct the subsequence
int prevoiusindex;
while (currindex >= 0)
{
result.add(arr[currindex]);
prevoiusindex = l[currindex].item2;
if (currindex == prevoiusindex)
break;
currindex = prevoiusindex;
}
for (int i = result.count - 1; i >= 0; i--)
console.write(result[i] " ");
}
static void main()
{
list arr = new list(new
int[] { 1, 101, 2, 3, 100, 4, 5 });
int n = arr.count;
// function call
constructmaxsumis(arr, n);
}
}
// this code is contributed by divyesh072019
output
1 2 3 100
时间复杂度:o(n2) t5】空间复杂度: o(n)
本文由阿迪蒂亚·戈尔供稿。如果你喜欢 geeksforgeeks 并想投稿，你也可以使用写一篇文章或者把你的文章邮寄到 contribute@geeksforgeeks.org。看到你的文章出现在极客博客pg电子试玩链接主页上，帮助其他极客。
如果你发现任何不正确的地方，或者你想分享更多关于上面讨论的话题的信息，请写评论。
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
