Largest Subarray with Zero Sum

How to find the suarray with maximum sum using divide and conquer

#include <stdio.h>
#include <limits.h>
 
// Utility function to find maximum of two numbers
int max(int x, int y) {
    return (x > y) ? x : y;
}
 
// Function to find maximum subarray sum using divide and conquer
int maximum_sum(int A[], int low, int high)
{
    // If array contains only one element
    if (high == low)
        return A[low];
 
    // Find middle element of the array
    int mid = (low + high) / 2;
 
    // Find maximum subarray sum for the left subarray
    // including the middle element
    int left_max = INT_MIN;
    int sum = 0;
    for (int i = mid; i >= low; i--)
    {
        sum += A[i];
        if (sum > left_max)
            left_max = sum;
    }
 
    // Find maximum subarray sum for the right subarray
    // excluding the middle element
    int right_max = INT_MIN;
    sum = 0;    // reset sum to 0
    for (int i = mid + 1; i <= high; i++)
    {
        sum += A[i];
        if (sum > right_max)
            right_max = sum;
    }
 
    // Recursively find the maximum subarray sum for left subarray
    // and right subarray and take maximum
    int max_left_right = max(maximum_sum(A, low, mid),
                            maximum_sum(A, mid + 1, high));
 
    // return maximum of the three
    return max(max_left_right, left_max + right_max);
}
 
// Maximum Sum Subarray using Divide & Conquer
int main(void)
{
    int arr[] = { 2, -4, 1, 9, -6, 7, -3 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    printf("The maximum sum of the subarray is %d", 
            maximum_sum(arr, 0, n - 1));
 
    return 0;
}

Source: techiedelight.com

Largest Subarray with Zero Sum

Largest subarray with sum 0

Input:
N = 8
A[] = {15,-2,2,-8,1,7,10,23}
Output: 5
Explanation: The largest subarray with
sum 0 will be -2 2 -8 1 7.

Source: practice.geeksforgeeks.org

Similar codes

1 vote163 views1 answer
How to read a comma delimited file into an array c++
C++
0 vote180 views1 answer
Std::iomanip c++
C++
0 vote175 views1 answer
Header for INT_MIN
C++
0 vote187 views1 answer
C++ scanf always expects double and not float
C++
0 vote198 views1 answer
Java to puthon converter
C++
0 vote156 views1 answer
What is stdoutread in c++
C++
-1 vote207 views1 answer
Templates of templates c++
C++
-3 votes198 views2 answers
Virtual function in C++
C++
1 vote176 views1 answer
Modulo Exponentiaon,Iteratve Modulo Exponentiation
C++
10 votes138 views2 answers
Last index of string c++
C++