Algorithm
problem Link : https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=1597
In a given sequence of non-negative integers you will have to find such a sub-sequence in it whose summation is maximum. Input The input file contains several input sets. The description of each set is given below: Each set starts with an integer N (N < 1000) that indicates how many numbers are in that set. Each of the next N lines contains a single non-negative integer. All these numbers are less than 10000. Input is terminated by a set where N = 0. This set should not be processed. Output For each set of input produce one line of output. This line contains one or more integers which is are taken from the input sequence and whose summation is maximum. If there is more than one such subsequence print the one that has minimum length. If there is more than one sub-sequence of minimum length, output the one that occurs first in the given sequence of numbers. A valid sub-sequence must have a single number in it. Two consecutive numbers in the output are separated by a single space.
Sample Input 2 3 4 0
Sample Output 3 4
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n,v;
while(cin >> n, n){
bool notEmpty = false;
for(int i=0;i < n;i++){
cin >> v;
if(v){
if(notEmpty) printf(" ");
notEmpty = true;
printf("%d",v);
}
}
if(!notEmpty) printf("0");
printf("\n");
}
}
Input
3
4
0
Output
Demonstration
UVA Online Judge solution - 10656-Maximum Sum (II) - UVA Online Judge solution in C,C++,java