Question Name:THE MAXIMUM SUB ARRAY

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main()
{
    int loop;
    cin >> loop;
    while (loop--) {
        int size;
        cin >> size;
        vector<int> data(size, 0);
        for (int i = 0; i < size; ++i) {
            cin >> data[i];
        }

        vector<int> dp(size, 0);
        int big = 0;
        int sum = 0;
        int start = -1;
        for (int i = 0; i < size; i++) {
            int val = sum + data[i];

            if (val > 0) {
                if (sum == 0) {
                    start = i;
                }
                sum = val;
            } else {
                sum = 0;
            }

            if (sum > big) {
                big = sum;
            }
        }

        if (start == -1) {
            cout << data[0] << " ";
        } else {
            cout << big << " ";
        }

        sum = 0;
        start = -1;
        for (int i = 0; i < size; ++i) {
            if (data[i] > 0) {
                start = i;
                sum += data[i];
            }
        }

        if (start == -1) {
            cout << data[0] << endl;
        } else {
            cout << sum << endl;
        }
    }
    return 0;
}
  • Problem Description
    Given an array A={a1,a2,…,aN} of N elements, find the maximum possible sum of a Contiguous subarray Non-contiguous 
    (not necessarily contiguous) subarray.

    Empty subarrays/subsequences should not be considered.

    Input Format

    First line of the input has an integer T. T cases follow. 
    Each test case begins with an integer N. In the next line, N integers follow representing the elements of array A.

    Constraints
    1<=T<=10 
    1<=N<=10^5 
    -10^4<=ai<=10^4
    The subarray and subsequences you consider should have at least one element.

    Output Format

    Two, space separated, integers denoting the maximum contiguous and non-contiguous subarray. At least one integer should be selected and put into the subarrays (this may be required in cases where all elements are negative).
  • Test Case 1
    Input (stdin)2
    4
    1 2 3 4
    6
    2 -1 2 3 4 -5
    Expected Output10 10
    10 11
  • Test Case 2
    Input (stdin)1
    6
    2 -1 2 3 4 -5
    Expected Output10 11

Leave a Reply

Your email address will not be published. Required fields are marked *

Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.

Powered By
CHP Adblock Detector Plugin | Codehelppro