Seemingly easy DP problem

[jagadish]

Given a sequence of integers and an integer P find the length longest streak S such that sum of numbers in S is <= P.

[Cosmin.ro]

Streak means subarray or subsequence? How large is N and P?

[jagadish]

streak is a sub-array .

Ex: if seq is 1 2 3 0 -1 -2 4 1 and P=1 ans is 4

N <10^5 and P<10^6*N [ i.e all vaues of in seq will be <10^6 ]

So bascially looking for a linear time algorithm

[ilovenwd]

Code: Select all

#include<stdio.h>
#include<stdlib.h>

const int maxN=1000000;
int a[maxN+1];

int check(int *a,int n,int p,int len)
{
	int i,j,k;
	for(i=1;i<n;i++) a[i]+=a[i-1];
	for(i=n;i>0;i--) a[i]=a[i-1];
	a[0]=0;
	int le=0;
	for(i=0;i<n;i++)
		for(j=i;j<n;j++)
			if(a[j+1]-a[i]<=p) {
				if(j+1-i>le) le=j+1-i;
			}
	return len==le;
}

void data(int *a,int &n,int &p)
{
	int i,j,k;
	n=rand()%1000+1;
	p=rand()%1000;
	for(i=0;i<n;i++) a[i]=rand()%1000;
}

int main()
{
	int i,j,n,p;
	for(int run=0;run<1000;run++) {
		data(a,n,p);
		// scanf("%d",&p);	for(i=0;i<n;i++) scanf("%d",&a[i]);
		int len=0,sum=0;
		int s=0,t=0;
		i=-1,j=0;
		while(i<n) { // invariant: sum(a[j]-a[i])<=p
			while(++i<n){
				sum+=a[i];
				if(sum>p) break;
			}
			if(i-j>len) s=j+1, t=i, len=i-j;
			while(sum>p) sum-=a[j++]; // keep the invariant
		}
		/*
		printf("n %d p %d\n",n,p);
		for(i=0;i<n;i++) printf("%4d",a[i]);
		printf("\n%d=>%d len: %d\n",s,t,len);
		*/

		if(!check(a,n,p,len)) printf("\nErr");
		
	}
}

[Renat]

If all number in the sequence are nonegative, then task can be easily solved with linear algorithm like ilovenwd's one.
In case of negative values there's following O(n*log(n)) algorithm:

Code: Select all

#include <vector>
#include <algorithm>
#include <cassert>
using namespace std;

struct prefix
{
	int sum,pos;
	prefix(int sum,int pos): sum(sum), pos(pos) {}	
	bool operator< (const prefix &pr) const
	{
		return (sum < pr.sum);
	}
};

int solve(vector<int> seq, int p)
{
	int n = seq.size();
	
	/* Find all prefix sums of given sequence and store them in vector ps. */
	vector<prefix> ps;
	ps.push_back(prefix(0, -1));
	int s = 0;
	for (int i = 0; i < n; ++i)
	{
		s += seq[i];
		ps.push_back(prefix(s, i));
	}
	
	/* Sort prefixes in nondecreasing order of sum. */
	sort(ps.begin(), ps.end());
	
	/* For every i: mp[i] = min(ps[i].pos, ps[i+1].pos, ...) */
	vector<int> mp(ps.size());
	int k = ps.back().pos;
	for (int i = ps.size() - 1; i >= 0; --i)
	{
		k = min(k, ps[i].pos);
		mp[i] = k;
	}
	
	/* Find longest streak with sum <= p. */
	int res = 0;
	int j = 0;
	for (int i = 0; i < ps.size(); ++i)
	{
		while (j < ps.size() && ps[i].sum - ps[j].sum > p) ++j;
		if (j >= ps.size()) break;
		res = max(res, ps[i].pos - mp[j]);
	}
	return res;
}