fork download
copy 
  1. import java.util.*;
  2.  
  3. public class Main {
  4.  
  5.     static final long MOD = 1000000007;
  6.  
  7.     public static void main(String[] args) {
  8.  
  9.         Scanner sc = new Scanner(System.in);
  10.  
  11.         int T = sc.nextInt();
  12.  
  13.         while (T-- > 0) {
  14.  
  15.             int n = sc.nextInt();
  16.  
  17.             long[] H = new long[n + 1];
  18.             long[] dp = new long[n + 1];
  19.  
  20.             for (int i = 1; i <= n; i++) {
  21.                 H[i] = sc.nextLong();
  22.             }
  23.  
  24.             for (int i = 1; i <= n; i++) {
  25.  
  26.                 // skip
  27.                 // means sum of prev subarray is grater than current h(i)+h(i-1)+dp(i-3)
  28.                 // so choose dp(i-3) + h(i-1) + h(i-2)
  29.                 dp[i] = dp[i - 1];
  30.  
  31.                 // take 2 houses
  32.                 if (i >= 2) {
  33.  
  34.                     long prev = 0;
  35.                     if (i - 3 >= 0) prev = dp[i - 3];
  36.  
  37.                     long val = prev + H[i] + H[i - 1];
  38.  
  39.                     dp[i] = Math.max(dp[i], val);
  40.                 }
  41.  
  42.                 // take 3 houses
  43.                 if (i >= 3) {
  44.  
  45.                     long prev = 0;
  46.                     if (i - 5 >= 0) prev = dp[i - 5];
  47.  
  48.                     long val = prev + H[i] + H[i - 1] + H[i - 2];
  49.  
  50.                     dp[i] = Math.max(dp[i], val);
  51.                 }
  52.  
  53.                 dp[i] %= MOD;
  54.             }
  55.  
  56.             System.out.println(dp[n] % MOD);
  57.         }
  58.     }
  59. }
Success #stdin #stdout 0.18s 56580KB
comments (?)
stdin
copy 
6
1
1
2
1 2
3
1 2 3
4
1 2 3 4 
5
4 1 1 5 6
5
1 5 5 5 1
stdout
copy 
0
3
6
9
16
15
https://ideone.com/2nM8o9
language:
Java (HotSpot 12)
created:
1 hour 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!