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
