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.