Maximum sum

Find the maximum sum that can be obtained by picking some non-empty subset of the array.

Example

Input: 5
1 2 -4 -2 3

Output: 6 3

Approach:

Java

public class MaxSum {
    static long cnt = 0;

    public static void main(String[] args) {
        long arr[] = { 1, 2, -4, -2, 3 };
        long maxSum = maxSum(arr);
        System.out.println("Max sum is " + maxSum + " " + cnt);

    }

    // Method to find max sum
    public static long maxSum(long[] arr) {
        long sum = 0;
        // Iterate till end of array
        for (int i = 0; i < arr.length; i++) {
            // if value is positive then add
            if (arr[i] >= 0) {
                sum += arr[i];
                cnt++;
            }
        }
        // if not found then return last element
        if (cnt == 0) {
            cnt = 1;
            long aux[] = new long[arr.length];
            mergeSort(arr, aux, 0, arr.length - 1);
            return arr[arr.length - 1];
        } else
            return sum;
    }

    // method for merge sort
    static void mergeSort(long arr[], long aux[], 
                            int low, int high) {
        // base case
        if (high <= low)
            return;
        int mid = low + (high - low) / 2;
        // left subarray
        mergeSort(arr, aux, low, mid);
        // right subarray
        mergeSort(arr, aux, mid + 1, high);
        // merge two sortd array
        mergeTwoSortedArray(arr, aux, low, mid, high);
    }

    static void mergeTwoSortedArray(long arr[], long aux[],
                     int low, int mid, int high) {
        int k = low, i = low, j = mid + 1;
        while (i <= mid && j <= high) {
            // if right subarray value is greater
            // the insert the left subarray into
            // the result
            if (arr[i] < arr[j]) {
                aux[k++] = arr[i];
                i++;
            }
            // otherwise insert the right subarray value
            // into the result
            else {
                aux[k++] = arr[j];
                j++;
            }
        }
        // if left subarray is remaining and right subaray is
        // over
        while (i <= mid)
            aux[k++] = arr[i++];
        // if right subarray is remaining and left subarray is
        // over
        while (j <= high)
            aux[k++] = arr[j++];
        // store result back to original array
        for (int l = low; l <= high; l++)
            arr[l] = aux[l];
    }

}

C++

#include <bits/stdc++.h>
using namespace std;
int main()
{
   long long n;
   cin>>n;
   long long a[n];
   long long sum=0,cnt=0;
   for(int i=0;i<n;i++)
      {
         cin>>a[i];
         if(a[i]>=0)
            {
              sum+=a[i];
              cnt++;
           }
      }
      sort(a,a+n);
   if(cnt==0)
         cout<<a[n-1]<<" "<<1<<"\n";
   else
     cout<<sum<<" "<<cnt<<"\n";


}