Some Basic DP Problem Solution

	///https://www.geeksforgeeks.org/k-th-largest-sum-contiguous-subarray/
	#include <bits/stdc++.h>
	using namespace std;
	#define INF 1<<30
	#define endl '\n'
	#define maxn 100005
	#define tc printf("Case %d: ", cs)
	#define tcn printf("Case %d:\n", cs);
	#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	typedef long long ll;
	const double PI = acos(-1.0);
	#define dbg(x) cerr << #x << " = " << x << endl;
	#define dbg2(x, y) cerr << #x << " = " << x << ", " << #y << " = " << y << endl;
	#define dbg3(x, y, z) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl;
	#define dbg4(w,x, y, z) cerr << #w << " = " << w << ", " <<#x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl;
	///O(n^2 log (k))
	int kthLargestSum(vector<int> v, int n, int k)
	{
	int sum[n + 1];
	sum[0] = 0;
	sum[1] = v[0];
	for (int i = 2; i <= n; i++)
	sum[i] = sum[i - 1] + v[i - 1];
	priority_queue<int, vector<int>, greater<int> > PQ;
	for (int i = 1; i <= n; i++) {
	for (int j = i; j <= n; j++) {
	int x = sum[j] - sum[i - 1];
	dbg(x);
	if ((int)PQ.size() < k) PQ.push(x);
	else {
	if (PQ.top() < x) {
	PQ.pop();
	PQ.push(x);
	}
	}
	}
	}
	return PQ.top();
	}
	int main()
	{
	FASTIO
	///*
	//double start_time = clock();
	#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	freopen("error.txt", "w", stderr);
	#endif
	//*/
	int n, k;
	cin >> n >> k;
	vector<int> v(n);
	for (int i = 0; i < n; i++) cin >> v[i];
	cout << kthLargestSum(v, n, k) << endl;
	//double end_time = clock();
	//printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000);
	return 0;
	}

view raw K-th Largest Sum Contiguous Subarray.cpp hosted with ❤ by GitHub

	///https://www.geeksforgeeks.org/largest-sum-contiguous-increasing-subarray/
	#include <bits/stdc++.h>
	using namespace std;
	#define INF 1<<30
	#define endl '\n'
	#define maxn 100005
	#define tc printf("Case %d: ", cs)
	#define tcn printf("Case %d:\n", cs);
	#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	typedef long long ll;
	const double PI = acos(-1.0);
	#define dbg(x) cerr << #x << " = " << x << endl;
	#define dbg2(x, y) cerr << #x << " = " << x << ", " << #y << " = " << y << endl;
	#define dbg3(x, y, z) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl;
	#define dbg4(w,x, y, z) cerr << #w << " = " << w << ", " <<#x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl;
	///O(n)
	int largestSUm(vector<int>const &v, int n)
	{
	//dbg(n);
	int ans = INT_MIN;
	for (int i = 0; i < n; i++) {
	int cur_sum = v[i];
	while (i + 1 < n && v[i + 1] > v[i]) {
	cur_sum += v[i+1];
	i++;
	//dbg3(cur_sum, v[i], i);
	}
	if (cur_sum > ans) ans = cur_sum;
	//i++;
	}
	return ans;
	}
	int main()
	{
	FASTIO
	///*
	//double start_time = clock();
	#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	freopen("error.txt", "w", stderr);
	#endif
	//*/
	int n, k;
	cin >> n >> k;
	vector<int> v(n);
	for (int i = 0; i < n; i++) cin >> v[i];
	cout << largestSUm(v, n) << endl;
	//double end_time = clock();
	//printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000);
	return 0;
	}

view raw Largest sum contiguous increasing subarray.cpp hosted with ❤ by GitHub

	#include <bits/stdc++.h>
	using namespace std;
	#define INF 1<<30
	#define endl '\n'
	#define maxn 100005
	#define tc printf("Case %d: ", cs)
	#define tcn printf("Case %d:\n", cs);
	#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	typedef long long ll;
	const double PI = acos(-1.0);
	#define dbg(x) cerr << #x << " = " << x << endl;
	#define dbg2(x, y) cerr << #x << " = " << x << ", " << #y << " = " << y << endl;
	#define dbg3(x, y, z) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl;
	#define dbg4(w,x, y, z) cerr << #w << " = " << w << ", " <<#x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl;
	/// -2 -3 4 -1 -2 1 5 -3
	// O(n)
	int maxSubArraySum(vector<int> const &v, int n)
	{
	int mx = INT_MIN;
	int x = 0;
	for (int i = 0; i < n; i++) {
	x = x + v[i];
	if (x > mx) mx = x;
	if (x < 0) x = 0;
	}
	return mx;
	}
	int maxSubArraySum2(vector<int> const &v, int n)
	{
	int mx = v[0];
	int cur_mx = v[0];
	for (int i = 1; i < n; i++) {
	cur_mx = max(v[i], cur_mx + v[i]);
	mx = max(mx, cur_mx);
	}
	return mx;
	}
	void maxSubArraySum3(vector<int> const &v, int n)
	{
	int mx = INT_MIN;
	int x = 0;
	int l = 0, r = 0, idx = 0;
	for (int i = 0; i < n; i++) {
	x = x + v[i];
	if (x > mx) {
	mx = x;
	l = idx;
	r = i;
	}
	if (x < 0) {
	x = 0;
	idx = i + 1;
	}
	}
	cout << mx << "{" << l << "," << r << "}\n";
	}
	int main()
	{
	FASTIO
	///*
	//double start_time = clock();
	#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	freopen("error.txt", "w", stderr);
	#endif
	//*/
	int n;
	cin >> n;
	vector<int> v(n);
	for (int i = 0; i < n; i++) cin >> v[i];
	int ans = maxSubArraySum(v, n);
	cout << ans << endl;
	ans = maxSubArraySum2(v, n);
	cout << ans << endl;
	maxSubArraySum3(v, n);
	//double end_time = clock();
	//printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000);
	return 0;
	}

view raw Largest Sum Contiguous Subarray hosted with ❤ by GitHub

Share: