fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int fms(int arr[], int n) 
  5. { 
  6.   int incl = arr[0]; 
  7.   int excl = 0; 
  8.   int excl_new; 
  9.   int i; 
  10.  
  11.   for (i = 1; i < n; i++) 
  12.   { 
  13.      /* current max excluding i */
  14.      excl_new = (incl > excl)? incl: excl; 
  15.  
  16.      /* current max including i */
  17.      incl = excl + arr[i]; 
  18.      excl = excl_new; 
  19.   } 
  20.  
  21.    /* return max of incl and excl */
  22.    return ((incl > excl)? incl : excl); 
  23. } 
  24.  
  25. int dp(int arr[], int n){
  26. 	int dp[1000] = {0};
  27. 	dp[1] = arr[1];
  28. 	for(auto i = 2; i < n; i++)
  29. 		dp[i] = max(dp[i-2] + arr[i], dp[i-1]);
  30.  
  31. 	return dp[n-1];
  32. }
  33.  
  34. int main(){
  35. 	int arr[10001] = {0};
  36. 	int n;
  37. 	cin >> n;
  38. 	for (auto i = 1; i<=n; i++) cin >> arr[i];
  39. 	cout << fms(arr, n+1) << endl;
  40. 	cout << dp(arr, n+1) << endl;
  41. }
Success #stdin #stdout 0s 4508KB
comments (?)
stdin
copy 
6
4 1 1 4 2 1
stdout
copy 
9
9
https://ideone.com/bqVDKj
language:
C++14 (gcc 8.3)
created:
6 years 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!