Advertisement
LEGEND2004

A - House Robber

Sep 6th, 2023 (edited)
748
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.52 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define int long long
  5. const int N = 1e6 + 5;
  6. const int mod = 1e9 + 7;
  7. const int INF = 1e18;
  8. int a[N];
  9. int dp[N];
  10.  
  11. signed main()
  12. {
  13.     int n;
  14.     cin >> n;
  15.     for(int i = 0; i < n; i++){
  16.         cin >> a[i];
  17.     }
  18.     int m = 0;
  19.     dp[0] = a[0];
  20.     for(int i = 1; i < n; i++){
  21.         dp[i] = m + a[i];
  22.         m = max(m , dp[i - 1]);
  23.     }
  24.     int ans = 0;
  25.     for(int i = 0; i < n; i++){
  26.         ans = max(ans , dp[i]);
  27.     }
  28.     cout << ans << endl;
  29. }
  30.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement