fork download
copy 
  1. import java.util.*;
  2. class Main {
  3.     static final long MOD = 1000000007;
  4.     public static void main(String[] args) {
  5.         Scanner sc = new Scanner(System.in);
  6.         int T = sc.nextInt();
  7.         while (T-- > 0) {
  8.             int n = sc.nextInt();
  9.             long[] H = new long[n + 1];
  10.             for (int i = 1; i <= n; i++) {
  11.                 H[i] = sc.nextLong();
  12.             }
  13.             long[][] dp = new long[n + 1][4];
  14.             long[] best = new long[n + 1];
  15.  
  16.             for (int i = 1; i <= n; i++) {
  17.  
  18.                 // take 2 houses ending at i
  19.                 if (i >= 2) {
  20.                     long prev = 0;
  21.                     if (i - 3 >= 0) {
  22.                         prev = best[i - 3];
  23.                     }
  24.                     dp[i][2] = H[i] + H[i - 1] + prev;
  25.                 }
  26.  
  27.                 // take 3 houses ending at i
  28.                 if (i >= 3) {
  29.                     long prev = 0;
  30.                     if (i - 5 >= 0) {
  31.                         prev = best[i - 5];
  32.                     }
  33.                     dp[i][3] = H[i] + H[i - 1] + H[i - 2] + prev;
  34.                 }
  35.  
  36.                 best[i] = best[i - 1];
  37.                 best[i] = Math.max(best[i], dp[i][2]);
  38.                 best[i] = Math.max(best[i], dp[i][3]);
  39.                 best[i] %= MOD;
  40.             }
  41.  
  42.             System.out.println(best[n] % MOD);
  43.         }
  44.     }
  45. }
Success #stdin #stdout 0.12s 54444KB
comments (?)
stdin
copy 
1
5
1 5 5 5 1
stdout
copy 
15
https://ideone.com/Db2hTS
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!