fork download
copy 
  1. import java.util.*;
  2. import java.lang.*;
  3. import java.io.*;
  4.  
  5. class Ideone
  6. {
  7.     // Main code
  8.     public static int solve1(int a[], int n){
  9.         if(n == 0) return 0;
  10.         if(n == 1) return a[0];
  11.  
  12.         int dp[] = new int[n];
  13.         dp[0] = a[0];
  14.         if(n >= 2){
  15.             dp[1] = Math.max(a[0], a[1]);
  16.         }
  17.         for(int i = 2; i < n; i++){
  18.             dp[i] = Math.max(dp[i-1], dp[i-2] + a[i]);
  19.         }
  20.         return dp[n-1];
  21.     }
  22.  
  23.     // Homework-1
  24.     public static int solve2(int a[], int n){
  25.         if(n == 0) return 0;
  26.         if(n == 1) return a[0];
  27.         if(n == 2) return Math.max(a[0] + a[1], a[1]);
  28.  
  29.         int dp[] = new int[n];
  30.         dp[0] = a[0];
  31.         dp[1] = Math.max(a[1], a[0] + a[1]);
  32.         dp[2] = Math.max(Math.max(a[2], a[0] + a[2]), a[1] + a[2]);
  33.  
  34.         for(int i = 3; i < n; i++){
  35.             dp[i] = Math.max(Math.max(dp[i-1], dp[i-2]), dp[i-3]) + a[i];
  36.         }
  37.         return dp[n-1];
  38.     }
  39.  
  40.     // Homework-2
  41.     public static int solve3(int a[], int n, List<Integer> blockedCells){
  42.         if(n == 0) return 0;
  43.         Set<Integer> set = new HashSet<>(blockedCells);
  44.  
  45.         int dp[] = new int[n];
  46.         Arrays.fill(dp, Integer.MIN_VALUE); 
  47.  
  48.         if(!set.contains(0)) dp[0] = a[0];
  49.         if(n >= 2 && !set.contains(1)) dp[1] = Math.max(dp[0], 0) + a[1];
  50.  
  51.         for(int i = 2; i < n; i++){
  52.             if(set.contains(i)) continue; 
  53.             int takePrev1 = dp[i-1] != Integer.MIN_VALUE ? dp[i-1] : 0;
  54.             int takePrev2 = dp[i-2] != Integer.MIN_VALUE ? dp[i-2] : 0;
  55.             dp[i] = Math.max(takePrev1, takePrev2) + a[i];
  56.         }
  57.  
  58.         return dp[n-1] != Integer.MIN_VALUE ? dp[n-1] : 0;
  59.     }
  60.  
  61.     public static void main (String[] args) throws java.lang.Exception
  62.     {
  63.         int[] arr1 = {3, 2, 5, 10, 7};
  64.         System.out.println("solve1 result: " + solve1(arr1, arr1.length)); 
  65.  
  66.         int[] arr2 = {1, 2, 9, 4, 5, 0, 3};
  67.         System.out.println("solve2 result: " + solve2(arr2, arr2.length)); 
  68.  
  69.         int[] arr3 = {3, 2, 7, 10, 12};
  70.         List<Integer> blocked = Arrays.asList(2); // block cell 2
  71.         System.out.println("solve3 result: " + solve3(arr3, arr3.length, blocked)); 
  72.     }
  73. }
  74.  
Success #stdin #stdout 0.12s 55724KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
solve1 result: 15
solve2 result: 23
solve3 result: 27
https://ideone.com/NJNf6l
language:
Java (HotSpot 12)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!