最大子序列总和,以使三个子序列都不连续


难度级别 中等
经常问 24 * 7创新实验室 Accenture 亚马逊 德里韦里 贝宝 PayU
排列 动态编程

问题“最大子序列总和使得没有三个是连续的”表示给您一个 排列 of 整数。 现在,由于您不能考虑三个连续元素,因此您需要找到一个具有最大总和的子序列。 回想一下,子序列不过是一个数组,当某些元素从原始输入数组中删除时,剩下的数组保持顺序不变。

使用案列

最大子序列总和,以使三个子序列都不连续

a[] = {2, 5, 10}
50

说明

选择5和10是一个容易的选择,因为任何其他方式都不会导致较大的总和。

a[] = {5, 10, 5, 10, 15}
40

说明

我们不选择数组中间的5。 因为那样会创建一个不满足问题条件的子序列。

途径

这个问题要求我们找到最大和的子序列,这样就不会选择三个连续的元素。 因此,幼稚的方法可能是产生子序列。 正如我们在前面的一些问题中所做的那样。 在大多数情况下,幼稚的方法是生成子序列,然后检查子序列是否满足问题中强加的条件。 但是这种方法很耗时,无法实际使用。 因为即使是中等大小的输入,使用该方法也会超出时间限制。 因此,要解决该问题,我们需要使用其他方法。

我们将使用 动态编程 要解决问题,但在此之前,我们需要执行一些案例工作。 完成此案例工作是为了将最初的问题减少到较小的子问题中。 因为在动态编程中,我们将问题简化为较小的子问题。 因此,请考虑跳过当前元素,然后将我们的问题简化为解决问题,直到找到上一个元素为止。 考虑一下,我们确实选择了当前元素。 然后,对于前一个元素,我们有两个选择。 我们要么选择前一个元素,要么这样做,那么我们就不能选择前一个元素之前的元素。 但是,如果我们不这样做,那么问题将被简化为解决问题,直到前一个元素到上一个元素为止。 使用代码会更容易理解。

代码

C ++代码查找最大子序列和,以使三个子序列都不连续

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int a[] = {1, 2, 3, 4, 5, 6};
    int n = sizeof(a) / sizeof(a[0]);
    int dp[n];

    // base case
    if(n>=0)dp[0] = a[0];
    if(n>0)dp[1] = a[0] + a[1];
    if(n>1)dp[2] = max({a[0] + a[1], a[2]+a[0], a[2]+a[1]});
    // if you choose a[i], then choose a[i-1] that is dp[i] = a[i]+a[i-1]+dp[i-3]
    // if you choose a[i], then you do not choose a[i-1] dp[i] = dp[i-2] + a[i]
    // if you do not choose a[i], dp[i] = dp[i-1]
    for (int i = 3; i < n; i++)
        dp[i] = max({a[i]+a[i-1]+dp[i-3], dp[i-2]+a[i], dp[i-1]});
    cout<<dp[n-1];
}
16

Java代码查找最大子序列和,以使三个子序列都不连续

import java.util.*;
class Main{
  public static void main(String[] args)
  {
    int a[] = {1, 2, 3, 4, 5, 6};
    int n = a.length;
    int dp[] = new int[n];

    // base case
    if(n>=0)dp[0] = a[0];
    if(n>0)dp[1] = a[0] + a[1];
    if(n>1)dp[2] = Math.max(Math.max(a[0] + a[1], a[2]+a[0]), a[2]+a[1]);
    // if you choose a[i], then choose a[i-1] that is dp[i] = a[i]+a[i-1]+dp[i-3]
    // if you choose a[i], then you do not choose a[i-1] dp[i] = dp[i-2] + a[i]
    // if you do not choose a[i], dp[i] = dp[i-1]
    for (int i = 3; i < n; i++)
        dp[i] = Math.max(Math.max(a[i]+a[i-1]+dp[i-3], dp[i-2]+a[i]), dp[i-1]);

    System.out.println(dp[n-1]);
  }
}
16

复杂度分析

时间复杂度

上), 因为我们只是遍历数组并继续填充我们的DP数组。 因此,时间复杂度是线性的。

空间复杂度

上), 因为我们必须制作一维DP数组来存储值。 空间复杂度也是线性的。