Largest sum subarray

QUESTION

Given an array, find the subarray (containing at least 5 numbers) which has the largest sum.

“TESTCASE_1”: “10\n5 1 23 5 47 4 3 1 2 12\n###—###SEPERATOR—###—\n103”, “TESTCASE_2”: “8\n12 15 14 30 4 19 23 10\n###—###SEPERATOR—###—\n127”, “TESTCASE_3”: “15\n1 7 8 9 4 3 20 14 15 12 56 8 104 10 2\n###—###SEPERATOR—###—\n273”, “TESTCASE_4”: “12\n562 421 563 52 47 89 103 254 477 1025 56 3\n###—###SEPERATOR—###—\n3652”, “TESTCASE_5”: “0\n###—###SEPERATOR—###—\n0

ANSWER

// C++ program to print largest contiguous array sum
#include<iostream>
#include<climits>
using namespace std;
 
int maxSubArraySum(int a[], int size)
{
    int max_so_far = INT_MIN, max_ending_here = 0;
 
    for (int i = 0; i < size; i++)
    {
        max_ending_here = max_ending_here + a[i];
        if (max_so_far < max_ending_here)
            max_so_far = max_ending_here;
 
        if (max_ending_here < 0)
            max_ending_here = 0;
    }
    return max_so_far;
}
 
/*Driver program to test maxSubArraySum*/
int main()
{
    
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
      cin>>a[i];
    int max_sum = maxSubArraySum(a, n);
    cout << max_sum;
    return 0;
}
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