fork download
copy 
  1. package dynamic_programming;
  2.  
  3. import java.util.*;
  4.  
  5. public class googleOAP1 {
  6.     public static int solution(int[] b, int n, int k) {
  7.         int[][] dp = new int[n + 1][k + 1];
  8.         for (int i = 1; i < n + 1; i++) {
  9.             for (int j = 1; j < k + 1; j++) {
  10.                 dp[i][j] = Integer.MIN_VALUE;
  11.             }
  12.         }
  13.         dp[0][0] = 0;
  14.         for (int l = 1; l <= k; l++) {
  15.             for (int i = 1; i <= n; i++) {
  16.                 int v = dp[i - 1][l];
  17.                 int sum = 0;
  18.                 for (int j = i; j >= 1; j--) {
  19.                     sum += b[j];
  20.                     v = Math.max(v, sum + dp[j - 1][l - 1]);
  21.                 }
  22.                 dp[i][l] = v;
  23.             }
  24.         }
  25.  
  26.         for (int i = 0; i < n + 1; i++) {
  27.             for (int j = 0; j < k + 1; j++) {
  28.                 System.out.print(dp[i][j] + " ");
  29.             }
  30.             System.out.println();
  31.         }
  32.         return dp[n][k];
  33.     }
  34.  
  35.     public static void main(String[] args) {
  36.  
  37.         Scanner scanner = new Scanner(System.in);
  38.  
  39.         int n, k;
  40.         n = scanner.nextInt();
  41.         k = scanner.nextInt();
  42.         int[] b = new int[n + 1];
  43.         for (int i = 1; i < n + 1; i++) {
  44.             b[i] = scanner.nextInt();
  45.         }
  46.         int ans = solution(b, n, k);
  47.         System.out.println(ans);
  48.     }
  49. }
  50.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
Main.java:5: error: class googleOAP1 is public, should be declared in a file named googleOAP1.java
public class googleOAP1 {
       ^
1 error
stdout
copy 
Standard output is empty
https://ideone.com/sjWybY
language:
Java (HotSpot 12)
created:
1 year ago
visibility:
secret

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!