17. Max Sum without Adjacents
The problem can be found at the following link: Question Link
My Approach
To find the maximum sum of elements in an array for this question, I use a dynamic programming approach. The idea is to maintain two variables, lastPrev
and prev
, representing the maximum sums excluding and including the last element, respectively. I iterate through the array, updating these variables at each step to consider the current element or skip it.
Time and Auxiliary Space Complexity
Time Complexity:
O(n)
, where n is the size of the array.Auxiliary Space Complexity:
O(1)
, as I only use a constant amount of extra space.
Code (C++)
class Solution {
public:
int findMaxSum(int *arr, int n) {
int lastPrev = 0;
int prev = arr[0];
int curr = 0;
for (int i = 1; i < n; ++i) {
curr = max(prev, arr[i] + lastPrev);
lastPrev = prev;
prev = curr;
}
return max(lastPrev, prev);
}
};
Contribution and Support
For discussions, questions, or doubts related to this solution, please visit our discussion section. We welcome your input and aim to foster a collaborative learning environment.
If you find this solution helpful, consider supporting us by giving a ⭐ star
to the getlost01/gfg-potd repository.
Last updated
Was this helpful?