Tổng tối đa sao cho không có hai phần tử nào liền kề trong C ++

Trong bài toán này, chúng ta được cung cấp một mảng arr []. Nhiệm vụ của chúng ta là tạo một chương trình để tìm Tổng tối đa sao cho không có hai phần tử nào liền nhau trong C ++.

Mô tả vấn đề

Chúng ta cần tìm tổng lớn nhất của dãy từ mảng sao cho không có 2 số nào từ dãy tổng là liền nhau trong mảng.

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

Đầu vào

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

Đầu ra

22

Giải thích

Taking sum sequence from index 0 with alternate elements : 5 + 3 + 9 + 5 = 22
Taking sum sequence from index 1 with alternate elements : 1 + 7 + 2 = 10

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

Để giải quyết vấn đề, chúng ta chỉ cần lặp qua tất cả các phần tử của mảng và duy trì hai tổng. sumVar1 và sumVar2, sumVar1 sẽ bao gồm tổng với phần tử hiện tại và sumVar2 sẽ bao gồm tổng mà không có phần tử hiện tại.

Với mỗi lần lặp, chúng tôi sẽ cập nhật sumVar2 là max (sumVar1, sumVar2). Và sau đó cập nhật sumVar1. Ở cuối vòng lặp, sumVar2 sẽ cung cấp tổng bắt buộc.

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 findmaximum(int a, int b){
   if(a > b)
      return a;
      return b;
}
int findMaxSumWOAdjecent(int arr[], int N){
   int maxSum1 = arr[0];
   int maxSum2 = 0;
   int temp;
   for (int i = 1; i < N; i++) {
      temp = findmaximum(maxSum1, maxSum2);
      maxSum1 = maxSum2 + arr[i];
      maxSum2 = temp;
   }
   return (findmaximum(maxSum1, maxSum2));
}
int main(){
   int arr[] = {5, 1, 3, 7, 9, 2, 5};
   int N = sizeof(arr) / sizeof(arr[0]);
   cout<<"The maximum sum such that no two elements are adjacent is "<<findMaxSumWOAdjecent(arr, N);
   return 0;
}

Đầu ra

The maximum sum such that no two elements are adjacent is 22