How do I print the numbers whose sum is equal to the maximum sum

Question

1.00/5 (3 votes)

See more:

In the XYZ society, the neighbours hate each other for their attitude. Various activities are organized in the society for Welcoming the New Year. The tickets were provided to each house with an integer written on it. Some got tickets with positive integers and some got tickets with negative integers. In the evening, people had to carry their tickets to the club house where the eligible ones will get the exciting gifts. The eligibility of winning the gift depends on the maximum sum which can be formed from the tickets numbers keeping in mind that neighbours hate each other. Since the neighbours hate each other, the two cannot be together in the list of maximum sum.

The President of the society, Mr. Singh, is a wise man and know that neighbours in society don't like each other. Also, he don't wish to become bad in front of people. So, he came up with an idea to design a program which will provide the list of integers forming maximum sum and thus all the members of the list will be given the gifts. The only problem with this idea is that he don't know programming so he is asking you to provide the correct list of integers. The people may be annoying but are smart and will fight if the list provided by you doesn't form the maximum sum.

Note: The integer written on ticket of individuals may or may not be unique. In case, when there are two list with equal maximum sum, the list with first greater element would be considered. For better understanding, look at the explanation of Test case 4 in Sample Test Case. The tickets with integer 0 are not considered for winning the gifts.

Input Format
The first line of input consist of number of test cases, T.
The first line of each test case consist of the number of houses (tickets distributed) in society, N.
The second line of each test case consist of N space separated tickets with integer written on them.

Constraints
1<= T <=10
1<= N <=10000
-1000<= Integer_on_Ticket <=1000

Output Format
For each test case, print the ticket numbers in a single line forming the maximum sum in the format similar to Sample Test Case.

What I have tried:

#include<iostream>

using namespace std;

void maxsum(int a[], int n);
int maxi(int a, int b);
int main()
{
   int t,n,i,j;
   
   cin>>t;
   
   while(t--)
   {
   	cin>>n;
   	
   	int a[n];
   	
   	for(i=0; i<n; i++)
   	cin>>a[i];
   	
   	maxsum(a,n);
   }

	
	return 0;
}
void maxsum(int a[], int n)
{
	int m[n],max=0,i,x[n],c=0;
	
	for(i=0; i<n; i++)
	x[i]=0;
	
	if(a[0]>0)
	m[0]=a[0];
	else
	m[0]=0;
	
	m[1]= maxi(a[1],a[0]);
	
	for(i=2; i<n; i++)
	{
		m[i]= maxi(m[i-1], m[i-2]+a[i]);
		
		max=m[i];
		
		if(max == m[i-1])
		{
			x[c]=i-1;
			c++;
		}
		else
		{
			x[c++]=i-2;
			x[c++]=i;
		}
		
	}
	
	//for(i=0; i<n; i++)
	//{
	//	if(max<m[i])
	//	max=m[i];
	//}
	//return max;
	
	for(int j=c; j>0; j--)
	{
		if(x[j]!=0)
		cout<<a[x[j]];
	}

}
int maxi(int a, int b)
{
	return (a>b?a:b);
}

Posted 24-Apr-19 8:30am

Kanishk Agrawal

Updated 27-Apr-19 7:57am

Add a Solution

Comments

phil.o 24-Apr-19 15:45pm

And what is your question?

Rick York 24-Apr-19 20:45pm

You should learn how to work with files. It's much easier to enter your testing data into a few files once than it is to type them in every time.

3 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Patrice T · Answer 1 · 2019-04-24T14:21:00

Quote:
How do I print the numbers whose sum is equal to the maximum sum

The problem is typical from a challenges sites, by definition, those challenges are complicated. The goal is always to create a specific algorithm that solve the problem.
This is an assignment given to you by you, the whole purpose is to know if you can solve it or not.
And obviously, you fail.

Unfortunately, solving the problem for you will never help your skills to solve other problems. Your fail just say that you need to study algorithms and practice.

Member 10251867 · Answer 2 · 2019-04-25T21:30:00

static int maxSubArraySum(int[] a, out List<int> res)
      {
          int size = a.Length;

          int max_so_far = 0, max_ending_here = 0;
          List<int> elements = new List<int>();

          for (int i = 0; i < size; i++)
          {
              max_ending_here = max_ending_here + a[i];
              if (a[i] > 0)
                  elements.Add(a[i]);

              if (max_ending_here < 0)
                  max_ending_here = 0;

              /* Do not compare for all elements. Compare only  when max_ending_here > 0 */
              else if (max_so_far < max_ending_here)
                  max_so_far = max_ending_here;
          }
          res = elements;
          return max_so_far;
      }
      public static void calculate()
      {
          try
          {
              int T = Convert.ToInt32(Console.ReadLine());
              if (T < 1 || T > 10) return;

              List<int> tickets = new List<int>();

              List<string> res = new List<string>();

              for (int loop = 0; loop < T; loop++)
              {
                  int count = Convert.ToInt32(Console.ReadLine());
                  if (count < 1 || count > 10000) continue;

                  tickets = Console.ReadLine().Split(' ').ToList().Where(x => !string.IsNullOrEmpty(x)).Select(x => Convert.ToInt32(x)).ToList();
                  if (tickets.Any(x => x < -1000 || x > 1000)) continue;

                  var evens = tickets.Where((s, i) => i % 2 == 0).ToArray();
                  var odds = tickets.Where((s, i) => i % 2 != 0).ToArray();

                  List<int> resEven = new List<int>();
                  List<int> resodd = new List<int>();

                  var resEvenSum = maxSubArraySum(evens, out resEven);
                  var resOddSum = maxSubArraySum(odds, out resodd);
                  var resR = "";

                  if (resEvenSum >= resOddSum)
                  {
                      for (int i = resEven.Count - 1; i >= 0; i--)
                      {
                          resR += resEven[i].ToString();
                      }
                  }
                  else if (resEvenSum < resOddSum)
                  {
                      for (int i = resodd.Count - 1; i >= 0; i--)
                      {
                          resR += resodd[i].ToString();
                      }
                  }

                  res.Add(resR);
              }
              for (int loop = 0; loop < res.Count; loop++)
              {
                  Console.WriteLine(res[loop].ToString().ToCharArray().Reverse().ToString());
              }

          }
          catch (Exception ex) { Console.Write(ex.Message + ex.StackTrace); }
      }

komalA18 · Answer 3 · 2019-04-27T07:58:00

 <pre>//sum of maximum neighburs
#include<iostream>
using namespace std;
void ins_Array(int Integer_on_Ticket[],int n)
{
 for(int i=0;i<n;i++)
    {
        cin>>Integer_on_Ticket[i];
        while(Integer_on_Ticket[i]<(-1000) || Integer_on_Ticket[i]>1000)
        {
            cout<<"enter again";
             cin>>Integer_on_Ticket[i];
        }
    }
}
int check(int Integer_on_Ticket[],int s[],int n)
{
    int m,k=0;
    for(int i=0;i<(n-2);i++)
    {
        for(int j=(i+2);j<n;j++)
        {
            s[k]=Integer_on_Ticket[i]+Integer_on_Ticket[j];
            if(s[k]<Integer_on_Ticket[i])
            {
                s[k]=Integer_on_Ticket[i];
            }
            k++;
        }
    }
    return k;
}
int sum(int Integer_on_Ticket[],int s[],int n,int k)
{
    int ma;
    ma=s[0];
    for(int i=0;i<k;i++)
    {
        if(ma<s[i])
        {
            ma=s[i];
        }
    }
    return ma;
}
int maxv(int Integer_on_Ticket[],int s[],int ma,int n,int k)
{
    int ans,f=0,p=0,r,t;
    for(int i=0;i<(n-2);i++)
    {
        for(int j=(i+2);j<n;j++)
        {
            ans=Integer_on_Ticket[i]+Integer_on_Ticket[j];
            if(ans==ma)
            {
                if(p==0)
                {
                //cout<<Integer_on_Ticket[j]<<Integer_on_Ticket[i]<<endl;
                r=i;
                t=j;
                f=1;
                p=1;
                }
                else if(p==1)
                {
                    if(Integer_on_Ticket[r]<Integer_on_Ticket[i])
                    {
                        r=i;
                        t=j;
                    }
                }
            }
        }
    }
    if(f==1)
    {
        cout<<Integer_on_Ticket[t]<<Integer_on_Ticket[r]<<endl;
    }
    return f;
}
int main()
{
    int n,Integer_on_Ticket[200],s[200],k,T;
    cout<<"enter no of test cases";
    cin>>T;
    while(T--)
    {
    cout<<"enter n";
    cin>>n;
    while(n<1 || n>1000)
    {
          cout<<"enter n";
          cin>>n;
    }
    ins_Array(Integer_on_Ticket,n);
    if(n==1)
    {
        cout<<Integer_on_Ticket[0];
    }
    else if(n==2)
    {
        cout<<"As neighbours hate each other";
    }
    else
    {
    k=check(Integer_on_Ticket,s,n);
    int ma=sum(Integer_on_Ticket,s,n,k);
    int j=maxv(Integer_on_Ticket,s,ma,n,k);
    if(j==0)
    {
        cout<<ma;
    }
    }
    }
    return 0;
}

How do I print the numbers whose sum is equal to the maximum sum

3 solutions

Solution 1

Solution 2

Solution 4

Add your solution here

Preview 0