fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int findMax(int arr[], int n, int k) 
  4. {
  5. 	int dp[k+1][n] = {};
  6. 	for(int i=0;i<k+1;i++){
  7. 		for(int j=0;j<n;j++)dp[i][j]=INT_MAX;
  8. 	}
  9. 	int sum1=0;
  10. 	for (int i=0;i<n;i++){
  11. 		sum1+=arr[i];
  12. 		dp[1][i]=sum1;
  13. 		// sum1+=arr[i];
  14. 	}
  15. 	// dp[0][n]=sum1;
  16. 	for(int i=2;i<=k;i++){
  17. 		for(int j=0;j<n;j++){
  18. 			int ans;
  19. 			sum1=arr[j];
  20. 			for(int l=j-1;l>=0;l--){
  21. 				ans=max(dp[i-1][l],sum1);
  22. 				dp[i][j]=min(dp[i][j],ans);
  23. 				sum1+=arr[l];
  24. 			}
  25. 			dp[i][j]=min(dp[i][j],sum1);
  26. 		}
  27. 	}
  28. 	return dp[k][n-1];
  29. }
  30.  
  31. int main() {
  32. 	int arr[] = { 10, 40, 10}; 
  33.     int n = sizeof(arr) / sizeof(arr[0]); 
  34.     int k = 2; 
  35.     cout << findMax(arr, n, k) << endl; 
  36. 	// your code goes here
  37. 	return 0;
  38. }
Success #stdin #stdout 0s 4352KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
50
https://ideone.com/T3uC1O
language:
C++14 (gcc 8.3)
created:
4 years 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!