在C ++中，前缀和前缀后给定元素的最大和增加子序列是必须的

在这个问题中，我们得到了一个由N个整数组成的数组arr []和两个索引值x和y。我们的任务是创建一个程序，以从前缀和在C ++中必须在前缀之后的给定元素中查找最大总和增加子序列。

问题描述

我们将找到直到索引x并包括索引y处的元素的递增序列的最大和。

让我们举个例子来了解这个问题，

输入值

arr[] = {1, 5, 9, 131, 6, 100, 11, 215}, x = 4, y = 6

输出结果

26

说明

我们将把子序列取到索引3，然后最后包含arr [6] = 11。

子序列为{1、5、9、11}。总和= 1 + 5 + 9 + 11 = 26

解决方法

一种简单的方法是在x索引之前创建一个新数组，然后在索引y的末尾添加元素。然后计算所有递增的子序列，然后丢弃所有不能包含元素arr [y]的子序列，并找到maxSum。

解决问题的一种更有效的方法是使用动态编程方法。这个想法是创建一个二维数组DP [] []，并存储增加的子序列的最大和。DP [x] [y]处的值将给出最大和，直到索引x包括元素arr [y]。

示例

该程序说明了我们解决方案的工作原理，

#include <iostream>
using namespace std;
int DP[100][100];
void preCalcMaxSum(int arr[], int N){
   for (int i = 0; i < N; i++) {
      if (arr[i] > arr[0])
         DP[0][i] = arr[i] + arr[0];
      else
         DP[0][i] = arr[i];
   }
   for (int i = 1; i < N; i++) {
      for (int j = 0; j < N; j++) {
         if (arr[j] > arr[i] && j > i) {
            if (DP[i - 1][i] + arr[j] > DP[i - 1][j])
               DP[i][j] = DP[i - 1][i] + arr[j];
            else
               DP[i][j] = DP[i - 1][j];
         }
         else
            DP[i][j] = DP[i - 1][j];
      }
   }
}
int main() {
   int arr[] = {1, 5, 9, 131, 6, 100, 11, 215};
   int N = sizeof(arr) / sizeof(arr[0]);
   int x = 4, y = 6;
   preCalcMaxSum(arr, N);
   cout<<"The maximum sum increasing subsequence from a prefix and a given element after prefix is must is ";
   cout<<DP[x][y];
   return 0;
}

输出结果

The maximum sum increasing subsequence from a prefix and a given element after prefix is must is 26

一种有效的方法是使用一种方法来找到直到索引x为止的递增子序列的最大和，以使序列的最大元素小于索引y处的元素。为此，我们将再次使用动态编程方法。

示例

该程序说明了我们解决方案的工作原理，

#include <iostream>
using namespace std;
int calcMaxSum(int arr[], int n, int x, int y){
   int DP[x] = {0};
   int maxSum = -1;
   for (int i = 0; i <= x; i++)
      DP[i] = arr[i];
   for (int i = 0; i <= x; i++) {
      if (arr[i] >= arr[y]) {
         continue;
      }
      for (int j = 0; j < i; j++) {
         if (arr[i] > arr[j])
            DP[i] += arr[j];
            maxSum = max(maxSum, DP[i]);
      }
   }
   if (maxSum == -1) {
      return arr[y];
   }
   return maxSum + arr[y];
}
int main(){
   int arr[] = {1, 5, 9, 131, 6, 100, 11, 215};
   int N = sizeof(arr) / sizeof(arr[0]);
   int x = 4, y = 6;
   cout<<"The maximum sum increasing subsequence from a prefix and a given element after prefix is must is ";
   cout<<calcMaxSum(arr, N, x, y);
   return 0;
}

输出结果

The maximum sum increasing subsequence from a prefix and a given element after prefix is must is 26