Find the maximum non consecutive sum from given Integer array
0. Navies solution and its run time is $\mathcal{O}(n^2) $
1. How the problem is related to maximum consecutive sum
2. How to come up the $\mathcal{O}(n)$ solution
How does it work in Dynamic Programming? Given an array \[ \{ n_0, n_1, \cdots, n_k, n_{k+1} \} \] Assume we can compute the max non-consecutive from \[ \{n_0, \cdots, n_k \}\] \[ max = MaxNonCon(\{n_0, \cdots, n_k \}) \] How we can compute the $\{ n_0, n_1, \cdots, \color{red}{n_k}, n_{k+1} \} $ if we know the maximum of non consecutive of $ \{n_0, \cdots, n_k\}$
Here is the trick
If $ n_k \in max $ then $ n_{k+1} $ can't be in $ max$ [ Non-consecutive ]
then the max of $\{ n_0, n_1, \cdots, \color{red}{n_k}, n_{k+1} \} $ is
\[ max = Max(max\,, n_{k+1}) \] if $ n_k \notin max $ then $ n_{k+1}$ could be included since $ \color{red}{n_{k}}$ separates $ \{n_0, \cdots, n_{k-1}\}$ and $ n_{k+1}$
so we have
\[ max = Max(max\,, max + n_{k+1}) \]
1. How the problem is related to maximum consecutive sum
2. How to come up the $\mathcal{O}(n)$ solution
How does it work in Dynamic Programming? Given an array \[ \{ n_0, n_1, \cdots, n_k, n_{k+1} \} \] Assume we can compute the max non-consecutive from \[ \{n_0, \cdots, n_k \}\] \[ max = MaxNonCon(\{n_0, \cdots, n_k \}) \] How we can compute the $\{ n_0, n_1, \cdots, \color{red}{n_k}, n_{k+1} \} $ if we know the maximum of non consecutive of $ \{n_0, \cdots, n_k\}$
Here is the trick
If $ n_k \in max $ then $ n_{k+1} $ can't be in $ max$ [ Non-consecutive ]
then the max of $\{ n_0, n_1, \cdots, \color{red}{n_k}, n_{k+1} \} $ is
\[ max = Max(max\,, n_{k+1}) \] if $ n_k \notin max $ then $ n_{k+1}$ could be included since $ \color{red}{n_{k}}$ separates $ \{n_0, \cdots, n_{k-1}\}$ and $ n_{k+1}$
so we have
\[ max = Max(max\,, max + n_{k+1}) \]
// [ ] {4} 5
//
// [4, 7]
// m = 4
// curr = 7
// max = 4
// => max = 7
// ---------------
// [4, 7, 5]
// m = 4
// curr = 7
// max = 4
// ------
// m = 7
// curr = 4 + 5
// max = 7
// => max(9, 7) = 9
// ---------------
public static int maxNonConsecutiveSum(int[] arr){
int max = 0;
if(arr != null && arr.length > 0){
int len = arr.length;
int pmax = 0;
max = arr[0];
for(int i=1; i<len; i++){
int m1 = Math.max(pmax + arr[i], arr[i]);
int m2 = Math.max(max, arr[i]);
pmax = max;
max = Math.max(m1, m2);
}
}
return max;
}
Find the maximum consecutive sum from given Integer array
This is similar question. Similar technic can be used to solve it
// 4, -5, 9, 7, -8, 3
//--------------------------------------------------------------------------------
// m = 0
// max = 0
//--------------------------------------------------------------------------------
// m = max(m, m+3) = 3
// max = 3
//--------------------------------------------------------------------------------
// m = max(m, m+-8) = -5 = 0
// max = 3
//--------------------------------------------------------------------------------
// m = max(m, m+7) = 7
// max = 7
//--------------------------------------------------------------------------------
// m = max(m, m+9) = 16
// max = 16
//--------------------------------------------------------------------------------
// m = max(m, m -5) = 11
// max = 16
//--------------------------------------------------------------------------------
// m = max(m, m + 4) = 15
// max = 16
//--------------------------------------------------------------------------------
public static int maxConsecutive(int[] arr) {
int m = 0;
int max = 0;
if(arr != null) {
for(int i=0; i<arr.length; i++) {
if(m + arr[i] > 0)
m = Math.max(m + arr[i], arr[i]);
else
m = 0;
if(m > max)
max = m;
}
}
return max;
}