UVA – 10684 – The jackpot

Problem Statement : http://uva.onlinejudge.org/external/106/10684.html
Type : Dynamic, Kadane Maximum Sub Sum

This is my best solution..

#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	int N, a, maxEver;
	while ((cin >> N) && N && !(maxEver=0)) {
		vector<int> v(N);
		while (N-- && (cin>>a))	v.push_back(a);
		for (size_t i = 1; i < v.size(); i++)
			v[i] = (v[i] + v[i-1] > v[i]) ? v[i] + v[i-1] : v[i];
		maxEver = *max_element(v.begin(), v.end());
		if(maxEver >0)	printf("The maximum winning streak is %d.\n", maxEver);
		else			printf("Losing streak.\n");
	}
	return 0;
}

Another detailed solution with the same order but with only one Pass using Kadane’s sum Algorithm

#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	int N, a;
	while ((cin >> N) && N) {
		vector<int> v(N);
		while (N-- && (cin>>a))	v.push_back(a);
		int maxEver=0, currentSum=0;
		for(size_t i=0; i<v.size(); i++){
			currentSum += v[i];
			maxEver = max(maxEver, currentSum);
			currentSum = currentSum <0 ? 0 : currentSum;
	        }
		if(maxEver >0)	printf("The maximum winning streak is %d.\n", maxEver);
		else			printf("Losing streak.\n");
	}
	return 0;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: