被 p1_kadane_algo.cpp 修订

没有变更

1 file changed, 56 insertions

p2_two_sum.cpp(文件已创建)

		@@ -0,0 +1,56 @@
1	+	#include <bits/stdc++.h>
2	+	using 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	+	bool 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	+	}
30	+	int 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	+	}

1 file changed, 65 insertions

p1_kadane_algo.cpp(文件已创建)

		@@ -0,0 +1,65 @@
1	+	#include <bits/stdc++.h>
2	+	using 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	+
19	+	long 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	+	}
43	+	void solve()
44	+	{
45	+	}
46	+	int 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	+	}

更新更早