Odd Sum SubSequence

problem statement:

You are given sequence *a[1]*, *a[2]*, ..., *a<[n]* of integer numbers of length *n*. Your task is to find such subsequence that its sum is odd and maximum among all such subsequences.
It's guaranteed that given sequence contains subsequence with odd sum.

Subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.

You should write a program which finds sum of the best subsequence.

Solution:

	#include <bits/stdc++.h>
	using namespace std;
	#define INF 1<<30
	#define MAX 10005
	#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	typedef long long ll;
	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;
	int mn = 100000000, mx = -100000000, sum = 0;
	for(int i = 0; i < n; i++){
	int x;
	cin >> x;
	if(x > 0){
	sum += x;
	if(x%2 == 1 && x < mn){
	mn = x;// small positive odd integer.
	}
	}
	else if(x < 0){
	if(abs(x)%2 == 1 && x > mx){
	mx = x; //Big Negeative odd integer.
	}
	}
	}
	if(sum%2 == 0){
	sum = max(sum-mn, sum+mx);
	}
	cout << sum << endl;
	//double end_time = clock();
	//printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000);
	return 0;
	}

view raw Odd Sum SubSequence.cpp hosted with ❤ by GitHub

Share: