Q-6 Maximum sum of non-adjacent elements - Coding Ninjas
Tue Aug 01 2023 06:58:12 GMT+0000 (Coordinated Universal Time)
Saved by
@Ayush_dabas07
import java.util.* ;
import java.io.*;
import java.util.*;
public class Solution {
public static int maximumNonAdjacentSum(ArrayList<Integer> nums) {
int n = nums.size();
// return s(nums , n-1 , new Integer[n]);
int dp[] = new int[n];
dp[0] = nums.get(0);
for(int i = 1 ;i < n ; i++){
int v = nums.get(i);
int c1 = v , c2 = 0;
if(i-2 >= 0)
c1 = v + dp[i-2];
if(i-1 >= 0)
c2 = 0 + dp[i-1];
dp[i] = Math.max(c1 ,c2);
}
return dp[n-1];
}
public static int s(ArrayList<Integer> nums , int i , Integer[] dp){
int v = nums.get(i);
if(i == 0){
return v;
}
if(dp[i] != null)
return dp[i];
//minium value will be that element itself
int c1 = v , c2 = 0; //take ,no take
if(i-2 >= 0)
c1 = v + s(nums , i-2 , dp);
if(i-1 >= 0)
c2 = 0 + s(nums ,i-1 , dp);
return dp[i] = Math.max(c1 ,c2);
}
}
content_copyCOPY
https://www.codingninjas.com/studio/problems/maximum-sum-of-non-adjacent-elements_843261
Comments