Raspu
BAN USER
Comments (3)
Reputation 0
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote
DP, recursive function:
f(n) = max( A[n] + f(n-2), A[n-1]+f(n-3) ), if n > 1
f(n) = A[0] , if n == 0
f(n) = 0 , if n < 0
C++ algorithm:
int maxSum(int arr [], int n)
{
int secArr [n+1];
//Base cases
secArr[0] = arr[0];
secArr[1] = max(arr[1],arr[0]);
secArr[2] = max(arr[2]+secArr[0],
arr[1]);
//Other cases
for (int i = 3; i <= n; i++)
{
secArr[i] = max(arr[i]+secArr[i-2],
arr[i-1]+secArr[i-3]);
}
return secArr[n];
}
Comment hidden because of low score. Click to expand.
Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
C++
- Raspu April 12, 2014