Subarray whose absolute sum is closest to K | C ++ code to find non - negative sub - array whose sum shows minimum deviation . This works only if all elements in array are non - negative ; Function to return the index ; Add Last element tp currSum ; Save Difference of previous Iteration ; Calculate new Difference ; When the Sum exceeds K ; Current Difference greater in magnitude . Store Temporary Result ; Difference in Previous was lesser In previous , Right index = j - 1 ; In next iteration , Left Index Increases but Right Index remains the Same Update currSum and i Accordingly ; Case to simply increase Right Index ; Check if lesser deviation found ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Pair { int f , s , t ; Pair ( int f , int s , int t ) { this -> f = f ; this -> s = s ; this -> t = t ; } } ; Pair * getSubArray ( int * arr , int n , int K ) { int currSum = 0 ; int prevDif = 0 ; int currDif = 0 ; Pair * result = new Pair ( -1 , -1 , abs ( K - abs ( currSum ) ) ) ; Pair * resultTmp = result ; int i = 0 ; int j = 0 ; while ( i <= j && j < n ) { currSum += arr [ j ] ; prevDif = currDif ; currDif = K - abs ( currSum ) ; if ( currDif <= 0 ) { if ( abs ( currDif ) < abs ( prevDif ) ) { resultTmp = new Pair ( i , j , currDif ) ; } else { resultTmp = new Pair ( i , j - 1 , prevDif ) ; currSum -= ( arr [ i ] + arr [ j ] ) ; i += 1 ; } } else { resultTmp = new Pair ( i , j , currDif ) ; j += 1 ; } if ( abs ( resultTmp -> t ) < abs ( result -> t ) ) { result = resultTmp ; } } return result ; } int main ( ) { int arr [ ] = { 15 , -3 , 5 , 2 , 7 , 6 , 34 , -6 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int K = 50 ; Pair * tmp = getSubArray ( arr , n , K ) ; int i = tmp -> f ; int j = tmp -> s ; int minDev = tmp -> t ; if ( i == -1 ) { cout << " The ▁ empty ▁ array ▁ shows ▁ minimum ▁ Deviation " << endl ; return 0 ; } for ( int k = i + 1 ; k < j + 1 ; k ++ ) { cout << arr [ k ] << " ▁ " ; } return 0 ; }