fork download
copy 
  1. import java.util.*;
  2. class Main {
  3.     public static void main(String[] args) {
  4.         Scanner sc = new Scanner(System.in);
  5.         int n = sc.nextInt();
  6.         long[] b = new long[n + 1];
  7.         for (int i = 1; i <= n; i++) {
  8.             b[i] = sc.nextLong();
  9.         }
  10.         if (n == 0) return;
  11.         long[][] dp = new long[n+1][4];
  12.         long ans = 0;
  13.         //cant take 2 or 3 houses yet  
  14.         //only at dp[2][2] i can take 2 houses
  15.         for (int i = 1; i <= n; i++) {
  16.             // if im taking 2 homes.. 
  17.             // h(i)+h(i-1)+dp[i-3] 
  18.             // since one gap between last used house i-2 skip
  19.             // (i>=2)th house and need 1 gap
  20.             if (i >= 2) {
  21.                 long best = 0;
  22.                 // since i can have gaps greater than one gap
  23.                 // i need to take max at each ith house
  24.                 //if i not yet reached i-3, then j could be 2-3.. so take max
  25.                 for (int j = Math.max(1, i - 3); j >= 1; j--){
  26.                     best = Math.max(best, dp[j][2]);
  27.                     best = Math.max(best, dp[j][3]);
  28.                 }
  29.                 dp[i][2] = b[i] + b[i - 1] + best;
  30.                 ans = Math.max(ans, dp[i][2]);
  31.             }
  32.  
  33.             if (i >= 3) {
  34.                 long best = 0;
  35.                 // if iter is not yet >=5 .. then cant go back 2 gaps yet
  36.                 //dont go in j loop yet
  37.                 for (int j = Math.max(1, i - 5); j >= 1; j--){
  38.                     best = Math.max(best, dp[j][2]);
  39.                     best = Math.max(best, dp[j][3]);
  40.                 }
  41.                 dp[i][3] = b[i] + b[i - 1] + b[i - 2] + best;
  42.                 ans = Math.max(ans, dp[i][3]);
  43.             }
  44.         }
  45.         System.out.println(ans);
  46.     }
  47. }
Success #stdin #stdout 0.12s 54556KB
comments (?)
stdin
copy 
5
1 5 5 5 1
stdout
copy 
15
https://ideone.com/c6PvaP
language:
Java (HotSpot 12)
created:
3 hours 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!