Maximum Sum

 Problem:-

You are given an array of integers 

A

, you need to find the maximum sum that can be obtained by picking some non-empty subset of the array. If there are many such non-empty subsets, choose the one with the maximum number of elements. Print the maximum sum and the number of elements in the chosen subset.

Input:

The first line contains an integer 

N

, denoting the number of elements of the array. Next line contains 

N

 space-separated integers, denoting the elements of the array.

Output:

Print 

2

 space-separated integers, the maximum sum that can be obtained by choosing some subset and the maximum number of elements among all such subsets which have the same maximum sum.

Constraints:

1N105

109Ai109

Sample Input
5
1 2 -4 -2 3
Sample Output
6 3
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

The chosen subset is {1, 2, 3}.

Code:-

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    long int a[n],sum=0,length=0,max;
    int flag=0;
    for(int i=0;i<n;i++)
    {
     cin>>a[i];
     // logic for finding maximumm
if(flag==0)
     {
         max=a[i];
         flag=1;
     }
     if(max<a[i])
     max=a[i];

     // if a[i] is greater than 0 than add it to the sum
     if(a[i]>=0)
     {
         sum=sum+a[i];
         length++;
     }
    }

    // if there is no any positive number then
    if(sum==0 && length==0)
    {
        cout<<max<<” “<<“1”;
    }

    // if a[i] have positive number then
    else
    cout<<sum<<” “<<length;
    return 0;
}



Leave a Reply

Your email address will not be published.