Find the Sub | C ++ program to find subarray with sum closest to 0 ; Function to find the subarray ; Pick a starting point ; Consider current starting point as a subarray and update minimum sum and subarray indexes ; Try all subarrays starting with i ; update minimum sum and subarray indexes ; Return starting and ending indexes ; Drivers code
#include <bits/stdc++.h> NEW_LINE using namespace std ; pair < int , int > findSubArray ( int arr [ ] , int n ) { int start , end , min_sum = INT_MAX ; for ( int i = 0 ; i < n ; i ++ ) { int curr_sum = arr [ i ] ; if ( min_sum > abs ( curr_sum ) ) { min_sum = abs ( curr_sum ) ; start = i ; end = i ; } for ( int j = i + 1 ; j < n ; j ++ ) { curr_sum = curr_sum + arr [ j ] ; if ( min_sum > abs ( curr_sum ) ) { min_sum = abs ( curr_sum ) ; start = i ; end = j ; } } } pair < int , int > p = make_pair ( start , end ) ; return p ; } int main ( ) { int arr [ ] = { 2 , -5 , 4 , -6 , -3 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; pair < int , int > point = findSubArray ( arr , n ) ; cout << " Subarray ▁ starting ▁ from ▁ " ; cout << point . first << " ▁ to ▁ " << point . second ; return 0 ; }