Ultima attività 1729533557

Revisione 6d2db12cf5f136db4ce8ede817846af10d8228c1

p1_kadane_algo.cpp Raw
1#include <bits/stdc++.h>
2using namespace std;
3#define ll long long
4#define mod 1000000007
5#define INF 1e18
6#define nl "\n"
7#define pb push_back
8#define eb emplace_back
9/*Note: emplace_back is faster than push_back*/
10#define ppb pop_back
11#define mp make_pair
12#define ff first
13#define ss second
14#define PI 3.141592653589793238462
15#define set_bits __builtin_popcountll
16#define sz(x) ((int)(x).size())
17#define all(x) (x).begin(), (x).end()
18
19long long maxSubarraySum(vector<int> &nums)
20{
21 int n = nums.size();
22 long long mx = LONG_MIN; // maximum sum
23 long long sum = 0;
24
25 for (int i = 0; i < n; i++)
26 {
27
28 sum += nums[i];
29
30 if (sum > mx)
31 {
32 mx = sum;
33 }
34
35 if (sum < 0)
36 {
37 sum = 0;
38 }
39 }
40
41 return mx;
42}
43void solve()
44{
45}
46int main()
47{
48 // ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
49#ifndef ONLINE_JUDGE
50 // freopen("input.txt", "r", stdin);
51 // freopen("output.txt", "w", stdout);
52#endif
53
54 ll t = 1;
55 cin >> t;
56 while (t--)
57 {
58 int n;
59 cin >> n;
60 vector<int> a(n);
61 for (int i = 0; i < n; i++)
62 cin >> a[i];
63 cout << maxSubarraySum(a) << nl;
64 }
65}
p2_two_sum.cpp Raw
1#include <bits/stdc++.h>
2using namespace std;
3#define ll long long
4#define mod 1000000007
5#define INF 1e18
6#define nl "\n"
7#define pb push_back
8#define eb emplace_back
9/*Note: emplace_back is faster than push_back*/
10#define ppb pop_back
11#define mp make_pair
12#define ff first
13#define ss second
14#define PI 3.141592653589793238462
15#define set_bits __builtin_popcountll
16#define sz(x) ((int)(x).size())
17#define all(x) (x).begin(), (x).end()
18bool sumUp(unordered_map<int, int> &mp, int k, vector<int> &nums)
19{
20 int n = nums.size();
21
22 for (int i = 0; i < n; i++)
23 {
24 int left = k - nums[i];
25 if (mp[left] > 0) // 1 pair summing up to k found
26 return true;
27 }
28 return false;
29}
30int main()
31{
32 // ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
33#ifndef ONLINE_JUDGE
34 // freopen("input.txt", "r", stdin);
35 // freopen("output.txt", "w", stdout);
36#endif
37
38 ll t = 1;
39 cin >> t;
40 while (t--)
41 {
42 int n, k; // n-->total number of elements, k-->sum of two numbers
43 cin >> n >> k;
44 vector<int> a(n);
45 unordered_map<int, int> mp; // stores the frequency of all the elements
46 for (int i = 0; i < n; i++)
47 {
48 cin >> a[i];
49 mp[a[i]]++;
50 }
51 if (sumUp(mp, k, a))
52 cout << "YES" << nl;
53 else
54 cout << "NO" << nl;
55 }
56}