Max Array Sum — HackerRank Medium Using Inplace Dynamic Programming
Hey guys, today we will be solving a problem called Max Array Sum. The link to this problem is:
This problem requires us to calculate the maximum sum among subsets of adjacent elements. What this means is that if an element in index 1 is in the subset, we cannot include the elements at index 0 or 2. This applies to the whole array. Thus, finding the subsets and calculating their sum and finding the highest one is basically our answer.
We will be doing this process using dynamic programming with in place approach.
What is inplace approach?
An inplace approach is not initializing another array to store our maximums, and keeping our memory cost to O(N) which is by default given to us. So basically we can also say keeping our memory cost O(1) since the array given is default.
How we can use this approach in the problem is that, when we reach a particular index in the array, and calculate the maximum sum up till that element, we can disregard all the elements that came before it as it already has the highest possible value stored in it. If we simply use the maximum value for each element from two steps back to calculate our current index i, then we will have our maximum at the end as we finish traversing the array.
We need to look at values two steps/indexes back because there cannot be adjacent elements in our subset.
For example:
3 7 4 6 5
As we start from begining
3 7 4 6 5 ( 3 max: base case)
3 7 4 6 5 ( 7 max : base case)
3 7 7 6 5 (3 + 4 = 7)
3 7 7 13 5 ( 7 + 6 = 13)
3 7 7 13 12 ( 5 + 7)
13 is our global max and this is the way we will be implementing our code.
if ( arr == null || arr.length == 0){ // Edge case return 0;}int n = arr.length;if (n == 1){ // Edge case return arr[0];}// Base case start from index 0 and 1int max = Math.max(arr[0], arr[1]); arr[1] = max;for (int i = 2; i < arr.length; i ++){ max = Math.max(arr[i-2] + arr[i], max); // Max uptill now max = Math.max(arr[i], max); // Max in special case where
// arr[i] + previous max is still less than arr[i]// update our inplace array with max for future calculations arr[i] = max;
}return max;
Thank you for reading! here is the video explanation:
