## Introduction

Welcome to this blog post, where we will explore a fascinating problem known as the Maximum Sum Problem with Non-adjacent Elements also known as kadane-II. We'll discuss the problem statement, dive into the step-wise solution, explain the code implementation, and conclude with key insights.

## Problem Statement

Given an array `arr` of size `sizeOfArr`, our goal is to find the maximum possible sum of a subsequence in the array, under the condition that we cannot include neighboring or adjacent elements in the sum. We must determine the maximum sum achievable while adhering to this constraint.

## Example

Input:

sizeOfArr = 4

arr[] = {4,5,6,7,8}

Output: 18

## Code

Here's the complete code implementation for solving the Maximum Sum Problem with Non-adjacent Elements:

#include <bits/stdc++.h>

using namespace std;

class Solution {

public:

long long maximumSum(int arr[], int n) {

long long res = 0;

vector<long long> dp(n, 0);

dp[0] = arr[0];

dp[1] = max(arr[0], arr[1]);

if (n == 1) {

return max(dp[0], dp[1]);

}

for (int i = 2; i < n; i++) {

dp[i] = max(max(dp[i - 2] + arr[i], (long long)arr[i]), dp[i - 1]);

}

return dp[n - 1];

}

};

int main() {

int sizeOfArray;

cin >> sizeOfArray;

int arr[sizeOfArray];

for (int i = 0; i < sizeOfArray; i++)

cin >> arr[i];

Solution ob;

cout << ob.maximumSum(arr, sizeOfArray) << endl;

return 0;

}

## Step-wise Solution

To solve the Maximum Sum Problem with Non-adjacent Elements, we can employ a dynamic programming approach. Follow the steps outlined below:

1. Initialize a variable `res` to store the maximum sum encountered during the calculation.

2. Create a vector `dp` of size `n` (the number of elements in the array), and initialize all elements to 0. The `dp` array will keep track of the maximum sum at each index.

3. Set `dp[0] = arr[0]` and `dp[1] = max(arr[0], arr[1])`. These initial values help kickstart the dynamic programming process.

4. If `n` is 1, return the maximum of `dp[0]` and `dp[1]`. This covers the case when the array has only one element.

5. Iterate from index 2 to `n-1`:

- Calculate `dp[i]` as the maximum of three values:

- `dp[i-2] + arr[i]`: If we include the current element, the maximum sum at index `i` is the sum of the current element and the maximum sum up to the previous non-adjacent element (`i-2`).

- `(long long) arr[i]`: If we exclude the current element, the maximum sum at index `i` is just the current element itself.

- `dp[i-1]`: If we exclude the current element, the maximum sum at index `i` is the same as the maximum sum at index `i-1`.

- Update `res` with the maximum value of `res` and `dp[i]`. This ensures that `res` always holds the maximum sum encountered so far.

6. Return `res` as the maximum sum, representing the solution to the problem.

## Conclusion

In this blog post, we explored the Maximum Sum Problem with Non-adjacent Elements. We discussed the problem statement, walked through a step-wise solution using dynamic programming, and provided a complete code implementation. By leveraging dynamic programming techniques, we can efficiently find the maximum sum of a subsequence while adhering to the constraint of not including adjacent elements. The solution has a time complexity of O(n) and a space complexity of O(n), where n represents the size of the input array.

visit and read this similar blog - kadane-I