Chuỗi con giảm dần tổng tối đa trong C ++

Trong bài toán này, chúng ta được cung cấp một mảng arr [] gồm N số nguyên. Nhiệm vụ của chúng ta là tìm Chuỗi con giảm dần tổng tối đa trong C ++.

Mô tả vấn đề

Chúng tôi sẽ tìm tổng số phần tử tối đa từ mảng sao cho dãy con giảm dần.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào

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

Đầu ra

17

Giải thích

Giảm dần dãy con với tổng tối đa là {10, 5, 2} =10 + 5 + 2 =17

Phương pháp tiếp cận giải pháp

Ở đây, chúng tôi sẽ sử dụng cách tiếp cận lập trình động để tìm ra giải pháp. Ở đây, chúng ta sẽ tạo một mảng maxSum [] sẽ lưu trữ maxSum cho đến chỉ mục i. Công thức sau được sử dụng để tìm các giá trị mảng,

maxSum [i] =arr [i] + max (maxSum [0… (* i-1)])

Tổng tối đa được cho bởi phần tử lớn nhất của mảng maxSum [].

Ví dụ

Chương trình minh họa hoạt động của giải pháp của chúng tôi,

#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;
}

Đầu ra

The maximum sum of decreasing subsequence is 106