Quick note first:
The post you link to only allows for positive numbers in input (with 0 also counting as possitive). Their proposed solution does work with a small adaptation that replaces any negative number with a 0 instead (where you just don't include the negative number in the maximum sum).
For example: The result is the same for arrays [1,0,-1,0,1]
and [1,0,0,0,1]
.
Asking us to write a different solution or asking how someone elses code works is off topic here. Instead I'll try to just provide some hints on how to get started on the constant space solution.
DISCLAIMER: None of the following code is tested. Copy at own risk (also indices in array are probably weird / inconsistent)
Let us consider a different question first that can be solved with a really similar strategy. Namely finding the n-th number of the really well known fibonaci sequence.
The most obvious solution is using recursion to calculate the previous 2 steps:
private static int recursiveFib(int n){
if(n<2){
return 1;
}
return recursiveFib(n-2)+recursiveFib(n-1);
}
The problem with this solution is that it will do the same calculations for smaller numbers over and over. You already recognised this and used an array to store intermediate results. That way you only need to calculate each number only once.
private static int recursiveFibMemorised(int n){
return recursiveFibMemorised(n, new int[n]);
}
private static int recursiveFibMemorised(int n, int[] known){
if(n<2){
return 1;
}
if(known[n]==0){
known[n] = recursiveFibMemorised(n-1, known) + recursiveFibMemorised(n-2,known);
}
return known[n];
}
The only problem left here is the recursive call itself. If we're smarter and start calculation from number 0 upwards we can guarantee that any previous ones are already stored. So instead of the recursive call we can directly look those up from the known array instead:
private static int recursiveFibMemorised2(int n){
int[] known = new int[n+1];
for(int i = 0; i<n; i++){
recursiveFibMemorised2(n, known);
}
return known[n];
}
private static int recursiveFibMemorised(int n, int[] known){
if(n<2){
return 1;
}
if(known[n]==0){
known[n] = known[n-1] + known[n-2];
}
return known[n];
}
Now that we got rid of the recursive call this looks kinda silly, so let's just do the calculation inside the loop directly instead:
private static int recursiveFibMemorised2(int n){
if(n<2) return 1;
int[] known = new int[n+1];
known[0]=1;
known[1]=1;
for(int i = 0; i<n; i++){
known[i]=known[i-1] + known[i-2];
}
return known[n];
}
Finally you can see that we only ever access the known array with the last 2 indices. Any previous value could be discarded. So let's use 2 ints instead of an entire array:
private static int optimisedFib(int n){
if(n<2){
return 1;
}
int prev2 = 1;
int prev1 = 1;
int current = 2;
for(int i = 2; i <= n ; i++){
current = prev2 + prev1;
prev2 = prev1;
prev1 = current;
}
return current;
}
A really similar strategy can now be used for your original problem. The most important thing to see is how to use a previously know max sum of a sub array. Take for example the array [5,1,1,4]
. If we first calculate the max sum of the subarray [5,1]
. This is 5. Than at the 4th element we can calculate the maximum as 4 + result of [5,1]
-> 9.
Notice that we're not interested in the value of the second element anymore there. Only in the max at that point. This means that we want to always store either the maximum value of the subarray 2 elements before + the current value; OR the maximum sum up to 1 element before but without adding the current element since it's adjacent.