C ++中的最大和减子序列

在这个问题中，我们得到了N个整数的数组arr []。我们的任务是找到C ++中的最大减总子序列。

问题描述

我们将从数组中找到元素的最大和，以使子序列严格减少。

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

输入项

arr[] = {3, 1, 6, 10, 5, 2, 9}

输出结果

17

说明

以最大和减少子序列为{10，5，2} = 10 + 5 + 2 = 17

解决方法

在这里，我们将使用动态编程方法来找到解决方案。在这里，我们将创建一个maxSum []数组，该数组将存储maxSum直到索引i。以下公式用于查找数组值，

maxSum [i] = arr [i] + max（maxSum [0…（* i-1）]）

最大和由数组maxSum []的最大元素给出。

示例

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

#include <iostream>
using namespace std;
int findMaxSumDecSubSeq(int arr[], int N){
   int maximumSum = 0;
   int maxSum[N];
   for (int i = 0; i < N; i++)
      maxSum[i] = arr[i];
   for (int i = 1; i < N; i++)
      for (int j = 0; j < i; j++)
         if (arr[i] < arr[j] && maxSum[i] < maxSum[j] + arr[i])
         maxSum[i] = maxSum[j] + arr[i];
   for (int i = 0; i < N; i++)
         if (maximumSum < maxSum[i])
            maximumSum = maxSum[i];
   return maximumSum;
}
int main(){
   int arr[] = { 5, 4, 100, 3, 2, 101, 1 };
   int N= sizeof(arr) / sizeof(arr[0]);
   cout<<"The maximum sum of decreasing subsequence is "<<findMaxSumDecSubSeq(arr, N);
   return 0;
}

输出结果

The maximum sum of decreasing subsequence is 106