fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define MAX 100005
  4. #define bitscount 32
  5. typedef long long ll;
  6.  
  7. // swap -> delete one element and/or insert another element 
  8. // -> we can delete one element    or  insert one element  or both  or do nothing
  9.  
  10. void solve() {
  11.     ll n;
  12.     cin >> n;
  13.     vector<ll> a(n + 1);
  14.     for (ll i = 1; i <= n; i++) cin >> a[i];
  15.     ll mx_del = 0, max_pref = 0;
  16.     // max subarray sum ending at i if we do nothing
  17.     vector<ll> dp_5aliyh(n + 1); 
  18.  
  19.     // max subarray sum ending at i if we  delete one elment
  20.     vector<ll> dp_na7iyh(n + 1); 
  21.  
  22.     // max subarray sum ending at i if we  add one elment
  23.     vector<ll> dp_ziydo(n + 1);
  24.  
  25.     // max subarray sum ending at i if we  delete one elment and add one element
  26.     vector<ll> dp_lzouz(n + 1); 
  27.  
  28.  
  29.  
  30.     vector<ll> ans(n + 1);
  31.     for (int i = 1; i <= n; i++) {
  32.         ans[i] = ans[i - 1];
  33.         dp_5aliyh[i] = max(dp_5aliyh[i - 1], 0LL) + a[i];
  34.         dp_na7iyh[i] = max(dp_na7iyh[i - 1] + a[i], dp_5aliyh[i] - a[i]);
  35.         dp_ziydo[i] = max(dp_ziydo[i - 1] + a[i], a[i] + max_pref);
  36.         dp_lzouz[i] = max({dp_lzouz[i - 1] + a[i], dp_ziydo[i - 1], dp_na7iyh[i - 1] + a[i]});
  37.  
  38.         //a[i]+mx_del : if the ith one will be added so take the max subarray that has one element deleted
  39.         // ---[abXcd]----M
  40.         // if M will be added after skipping some element so take the max subarray that has one element deleted
  41.         // -> swap M with X 
  42.         ans[i] = max({ans[i], dp_5aliyh[i],dp_ziydo[i],dp_na7iyh[i], dp_lzouz[i], a[i] + mx_del});
  43.         max_pref = max(max_pref, a[i]);
  44.         mx_del = max(mx_del, dp_na7iyh[i]);
  45.     }
  46.     for (int i = 1; i <= n; i++) {
  47.         cout << ans[i] << " ";
  48.     }
  49.     cout << "\n";
  50. }
  51.  
  52. int main() {
  53.     ios::sync_with_stdio(false);
  54.     cin.tie(nullptr);
  55.     int t=1;
  56.     //cin >> t;
  57.     while (t--) solve();
  58.     return 0;
  59. }
  60.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin 
Standard input is empty
stdout 

	

		
	 
	
	
			

					
			
			
			
			
			
			
			
			

			
			
			
		

	
		
		

			


			                        
			
			

				

	
					
					 https://ideone.com/8m4vMI
					
					
					
					
					

												

												
						
						

					

					
					
					

						
language:

						
C++ (gcc 8.3)

					

					

						
created:
								
						
5 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!