I was doing a question online. The question was:

Given an integer array A of size N. You have to pick exactly B elements from either left or right end of the array A to get maximum sum.
Find and return this maximum possible sum.
NOTE: Suppose B = 4 and array A contains 10 elements then you can pick first four elements or can pick last four elements or can pick 1 from front and 3 from back etc . you need to return the maximum possible sum of elements you can pick.

The link for the same is this.

I wrote the following code with the approach to find minimum contiguous sum of subarray of size total array size-B using sliding window and subtracting that sum from the total sum to get the maximum required sum.:

int Solution::solve(vector<int> &A, int B) {
    long long sum=0;
    for(int a:A)
    {
       sum =a;   //sum of all the elements
    }
    int window=A.size()-B;  
    int j=0;
    long long mini=LONG_MAX;
    long long cur=0; //cur stores sum of current window
    for(int i=0;i<A.size();i  )
    {
        cur =A[i];  //increase window size by 1
        if(i>=window-1)
        {
            mini=min(mini,cur);
            cur-=A[j];
            j  ;    //decrease window size by 1
        }
    }
    return sum-mini;
}

The above code failed for a really large test case :

A : [ -819, -26, 0, -659, -538, -570, -955, -114, -492, -211, -546, -258, -526, -175, -944, -438, -279, -711, -345, -489, -848, -519, -492, -172, -125, -655, -814, -869, -100, -19, -358, -948, -280, -532, -25, -487, -463, -770, -662, -686, -760, -437, -337, -211, -738, -457, -496, -903, -920, -499, -315, -828, -896, -657, -948, -312, -991, -902, -295, -214, -153, -180, -525, -348, -434, -81, -893, -558, -901, -316, -637, -716, -10, -965, -927, -271, -726, -121, -235, -492, -289, -520, -926, -830, -727, -227, -940, -253, -166, -285, -575, -52, -838, -7, -137, -414, -168, -964, -757, -708, -804, -863, -916, -594, -267, -883, -871, -484, -114, -966, -631, -251, -55, -241, -330, -986, -412, -917, -587, -734, -27, -485, -508, -569, -631, -311, -157, -920, -525, -267, -232, -200, -595, -963, -688, -125, -290, -620, -330, -624, -866, -52, -163, -93, -487, -913, -214, -180, -503, -993, -974, -703, -91, -329, -55, -723, -87, -556, -253, -835, -196, -851, -94, -518, -464, -993, 0, -591, -887, -345, -254, -12, -446, -670, -916, -634, -23, -43, -197, -312, -688, -835, -184, -848, -820, -977, -391, -216, -934, -315, -128, -728, -360, -483, -721, -118, -350, -80, -811, -574, -502, -287, -424, -911, -149, -560, -843, -890, -237, -883, -465, -430, -928, -138, -329, -57, -936, -612, -902, -463, -808, -205, -765, -766, -254, -448, -812, -528, -525, -73, -106, -952, -195, -637, -29, -957, -460, -733, -1000, -491, -286, -108, -336, -78, -637, -709, -757, -226, -159, -559, -479, -726, -474, -362, -772, -412, -223, -965, -620, -932, -505, -93, -139, -453, -570, -412, -779, -895, -715, -207, -341, -611, -206, -304, -609, -448, -481, -689, -69, -172, -752, -573, -487, -608, -424, -485, -662, -268, -732, -909, -344, -946, -947, -935, -188, -638, -281, -527, -472, -133, -602, -507, -67, -821, -967, -18, -89, -108, -115, -146, -496, -728, -556, -401, -372, -747, -23, -984, -14, -997, -812, -755, -262, -534, -551, -796, -386, -567, -224, -794, -477, -575, -304, -832, -549, -903, -11, -122, -15, -842, -395, -785, -477, -636, -941, -36, -160, -178, -583, -216, -664, -673, -185, -660, -520, -235, -449, -491, -388, -63, -584, -832, -973, -381, -73, -939, -757, -898, -83, -975, -129, -115, -594, -597, -694, -545, -981, -383, -862, -973, -344, -483, -240, -353, -709, -951, -38, -415, -740, -843, -394, -647, -906, -678, -545, -721, -341, -765, -632, -969, -906, -730, -515, -627, -673, -7, -366, -727, -530, -905, -333, -709, -363, -418, -803, -763, -74, -980, -903, -717, -297, -36, -83, -957, -237, -673, -204, -181, -339, -146, -253, -884, -386, -206, -973, -719, -839, -494, -973, -686, -530, -213, -54, -336, -810, -12, -248, -494, -445, -766, -797, -132, -792, -383, -220, -901, -551, -964, -196, -719, -745, -647, -820, -643, -45, -864, -681, -952, -294, -334, -962, -866, -540, -227, -481, -441, -851, -150, -264, -752, -946, -770, -530, -918, -791, -19, -649, -967, -614, -924, -679, -860, -338, -129, -804, -858, -523, -788, -813, -56, -711, -188, -854, -719, -375, -906, -690, -702, -819, -125, -870, -136, -819, -131, -637, -161, -148, -441, -225, -381, -301, -640, -324, -992, -612, -81, -6, -997, -609, -499, -79, -571, -815, -388, -781, -953, -353, -689, -617, -154, -416, -145, -618, -400, -628, -690, -666, -214, -753, -264, -189, -590, -427, -505, -228, -900, -967, -993, -770, -213, -571, -724, -863, -56, -834, -881, -64, -51, -492, -703, -644, -245, -80, -777, -132, -449, -107, -678, -532, -754, -599, -121, -773, -481, -293, -203, -663, -959, -366, -827, -361, -222, -159, -64, -435, -393, -780, -53, -965, -137, -383, -657, -451, -931, -628, -931, -963, -931, -849, -976, -768, -671, -115, -365, -128, -704, -249, -193, -172, -394, -493, -123, -386, -973, -732, -814, -260, -415, -500, -923, -507, -292, -262, -326, -940, -408, -260, -406, -600, -865, -377, -104, -232, -542, -505, -322, -632, -274, -339, -227, -84, -498, -304, -151, -991, -898, -719, -217, -251, -646, -814, -728, -855, -233, -365, -227, -827, -272, -215, -348, -333, -411, -340, -793, -531, -127, -93, -243, -578, -193, -593, -215, -487, -593, -524, -762, -318, -694, -448, -526, -549, -257, -910, -486, -297, -328, -717, -364, -680, -940, -281, -906, -939, -287, -170, -156, -842, -750, -195, -551, -279, -785, -805, -326, -228, -772, -704, -230, -642, -985, -935, -504, -540, -422, -607, -602, -914, -721, -244, -38, -381, -61, -754, -515, -919, -55, -509, -328, -484, -647, -640, -9, -269, -778, -412, -191, -172, -56, -396, -750, -844, -706, -256, -736, -806, -375, -2, -992, -277, -471, -265, -705, -122, -929, -751, -537, -645, -55, -728, -6, -135, -542, -557, -458, -727, -391, -629, -656, -991, -507, -640, -390, -349, -671, -623, -782, -608, -570, -216, -99, -500, -935, -250, -187, -985, -873, -52, -863, -362, -840, -31, -605, -625, -393, -92, -229, -930, -882, -557, -180, -931, -30, -580, -860, -285, -247, -638, -217, -925, -727, -397, -165, -596, -779, -217, -479, -673, -349, -518, -419, -757, -815, -414, -666, -203, -302, -661, -191, -24, -142, -103, -899, -611, -375, -400, -42, -833, -274, -451, -826, -522, -711, -553, -463, -820, -426, -67, -82, -181, -133, -395, -426, -154, -476, -840, -807, -356, -466, -96, -582, -369, -229, -179, -330, -168, -612, -259, -808, -644, -151, -472, -584, -141, -864, -430, -348, -948, -274, -34, -478, -285, -553, -419, -692, -99, -512, -201, -563, -287, -849, -890, -243, -939, -880, -553, -213, -997, -23, -830, -257, -50, -944, -291, -28, -95, -165, -318, -309, -396, -361, -309, -587, -670, -417, -685, -546, -939, -69, -354, -886, -924, -574, -243, -866, -158, -853, -163, -199, -541, -486, -439, -230, -642, -509, -802, -51, -373, -321, -160, -515, -299, -403, -56, -928, -367, -843, -789, -717, -149, -291, -109, -7, -475, -948, -511, -592, -782, -766, -996, -907, -232, -452, -340, -330, -404, -666, -799, -164, -517, -680, -36, -959, -434, -476, -497, -341, -46, -684, -235, -280, -710, -386, -672, -62, -390, -485, -509, -437, -489, -97, -637, -150, -354, -831, -385, -889, -153, -955, -718, -488, -246, -314, -554, -80, -392, -540, -585, -989, -406, -304, -626, -584, -769, -838, -2, -300, -839, -15, -606, -248, -323, -616, -314, -115, -874, -354, -663, -384, -516, -368, -922, -141, -586, -462, -126, -110, -778, -315, -930, -673, -817, -24, -964, -709, -766, -972, -383, -688, -780, -589, -866, -834, -708, -774, -833, -940, -89, -188, -909, -182, -515, -385, -670, -90, -451, -603, -523, -530, -660, -511, -586, -664, -958, -213, -951, -858, -949, -918, -939, -730, -922, -310, -867, -917, -873, -127, -325, -224, -559, -753, -725, -708, -708, -959, -513, -119, -428, -901, -849, -307, -566, -481, -505, -527, -426, -483, -158, -221, -813, -327, -923, -299, -724, -118, -934, -390, -995, -114, -602, -847, -95, -215, -489, -719, -250, -926, -975, -350, -403, -11, -172, -838, -655, -235, -498, -783, -237, -570, -289, -379, -67, -570, -85, -197, -153, -876, -47, -137, -799, -369, -136, -117, -670, -964, -305, -277, -482, -50, -284, -126, -816, -529, -979, -174, -892, -302, -930, -463, -638, -781, -393, -612, -717, -77, -211, -463, -135, -808, -426, -235, -725, -193, -663, -281, -496, -462, -315, -201, -497, -39, -999, -992, -411, -809, -147, -216, -937, -479, -159, -503, -790, -991, -700, -665, -346, -490, -724, -5, -117, -170, -765, -222, -615, -736, -416, -932, -144, -776, -172, -149, -566, -25, -356, -596, -647, -127, -462, -255, -499, -550, -49, -656, -621, -168, -444, -247, -241, -993, -407, -80, -3, -414, -131, -263, -828, -132, -342, -514, -997, -525, -557, -192, -879, -176, -193, -133, -27, -991, -758, -747, -479, -323, -496, -578, -870, -523, -952, -20, -70, -798, -432, -505, -610, -648, -562, -97, -109, -116, -381, -731, -633, -395, -806, -238, -126, -852, -641, -443, -239, -421, -912, -709, -915, -131, -875, -435, -841, -674, -992, -573, -674, -947, -331, -39, -5, -852, -980, -397, -657, -102, -609, -920, -30, -233, -143, -884, -634, -643, -589, -161, -894, -163, -744, -484, -728, -766, -55, -626, -617, -357, -661, -62, -188, -126, -912, -841, -764, -162, -47, -570, -897, -915, -862, -545, -845, -577, -161, -941, -932, -420, -837, -807, -781, -749, -342, -223, -315, -359, -974, -744, -277, -500, -589, -628, -388, -234, -231, -213, -224, -1, -927, -190, -405, -149, -157, -99, -627, -203, -640, -938, -68, -817, -979, -96, -620, -547, -254, -115, -670, -4, -238, -357, -531, -511, -290, -629, -599, -865, -702, -562, -999, -173, -537, -432, -251, -199, -772, -948, -245, -403, -984, -662, -189, -695, -897, -701, -580, -682, -341, -387, -249, -696, -901, -625, -134, -886, -155, -302, -237, -779, -59, -680, -238, -881, -462, -888, -584, -381, -211, -256, -722, -494, -880, -821, -936, -997, -527, -952, -237, -400, -390, -72, -115, -797, -162, -245, -696, -137, -544, -106, -717, -748, -425, -128, -824, -164, -471, -848, -649, -345, -479, -134, -220, -184, -336, -444, -636, -799, -436, -488, -702, -679, -195, -453, -443, -251, -147, -39, -476, -208, -887, -902, -900, -820, -189, -466, -703, -260, -770, -51, -650, -661, -147, -239, -917, -494, -241, -562, -157, -657, -457, -373, -296, -597, -622, -525, -550, -938, -646, -772, -391, -302, -159, -29, -472, -883, -398, -699, -890, -989, -801, -758, -936, -355, -895, -983, -184, -220, -89, -32, -723, -532, -452, -984, -803, -928, -781, -584, -528, -863, -796, -530, -520, -489, -728, -792, -34, -601, -222, -862, -402, -896, -893, -941, -549, -454, -979, -512, -618, -181, -670, -302, -741, -387, -449, -713, -310, -351, -567, -755, -392, -934, -240, -337, -255, -347, -754, -915, -694, -245, -706, -239, -65, -6, -560, -830, -424, -988, -852, -315, -617, -97, -963, -286, -976, -180, -927, -223, -746, -353, -935, -997, -631, -660, -272, -211, -792, -526, -56, -631, -455, -639, -52, -441, -648, -645, -416, -870, -10, -628, -748, -78, -898, -152, -868, -330, -499, -656, -558, -365, -889, -474, -571, -265, -695, -975, -802, -580, -501, -84, -514, -812, -210, -572, -814, -546, -614, -778, -454, -340, -185, -144, -435, -354, -592, -458, -195, -302, -308, -175, -506, -244, -523, -761, -777, -468, -369, -922, -975, -379, -258, -981, -505, -236, -595, -139, -275, -629, -95, -975, -538, -442, -328, -177, -881, -934, -537, -869, -585, -83, -845, -137, -318, -723, -219, -494, -949, -795, -969, -697, -31, -421, -21, -61, -191, -408, -751, -942, -911, -662, -433, -642, -765, -139, -204, -815, -331, -51, -676, -500, -985, -193, -753, -630, -576, -159, -786, -921, -739, -413, -968, -132, -186, -10, -567, -83, -42, -81, -37, -347, -210, -40, -717, -459, -539, -25, -628, -546, -776, -396, -710, -445, -683, -559, -125, -686, -866, -713, -465, -746, -326, -842, -615, -926, -232, -947, -47, -741, -897, -497, -279, -611, -568, -568, -46, -786, -744, -712, -832, -511, -366, -186, -317, -833, -789, -517, -528, -809, -259, -57, -849, -305, -103, -519, -686, -222, -608, -292, -314, -476, -476, -440, -18, -95, -630, -929, -315, -801, -381, -176, -992, -470, -795, -772, -231, -656, -769, -723, -543, -402, -119, -886, -602, -354, -382, -862, -891, -466, -396, -285, -524, -722, -916, -551, -925, -949, -927, -260, -957, -490, -92, -342, -379, -712, -267, -322, -845, -745, -353, -548, -488, -359, -147, -457, -692, -464, -237, -494, -499, -331, -706, -818, -448, -76, -769, -946, -478, -600, -139, -367, -12, -101, -174, -594, -954, -607, -185, -323, -418, -78, -308, -163, -509, -437, -269, -23, -538, -469, -109, -869, -928, -267, -826, -887, -52, -438, -217, -446, -970, -546, -210, -327, -176, -651, -663, -493, -331, -178, -882, -116, -961, -674, -801, -442, -279, -545, -321, -751, -743, -88, -232, -527, -74, -104, -926, -995, -486, -699, -653, -126, -507, -75, -420, -362, -272, -416, -361, -703, -141, -923, -93, -40, -817, -109, -294, -223, -99, -883, -400, -430, -203, -880, -44, -834, -939, -284, -981, -970, -98, -931, -421, -945, -384, -389, -46, -104, -613, -84, -319, -63, -147, -432, -125, -88, -320, -292, -461, -991, -301, -985, -984, -517, -337, -649, -986, -569, -408, -311, -934, -90, -421, -995, -247, -628, -926, -714, -299, -818, -407, -989, -729, -54, -667, -539, -681, -245, -740, -651, -96, -804, -354, -217, -720, -670, -794, -787, -318, -8... ]
B : 

The expected return value: 
-50293468
Your function returned the following: 
-50292468

I made minor changes by first calculating the 1st window sum in a separate loop, then assigning it as minimum and then doing the rest of process and it worked. The code which worked is below:

int Solution::solve(vector<int> &A, int B) {
    long long sum=0;
    for(int a:A)
    {
        sum =a;
    }

    int window=A.size()-B;
    int j=0;
    long long mini;
    long long cur=0;
    for(int i=0;i<=window-1;i  )
    {
        cur =A[i];
    }
    mini=cur;
    for(int j=0,i=window;i<A.size();i  ,j  )
    {
        cur =A[i];
        cur-=A[j];
        mini=min(mini,cur);
    }
    return sum-mini;
    
}

Please tell where the first code was wrong. I tried a lot, but couldn't find on my own.

CodePudding user response：

There's an edge case in your first solution:

When B == A.size(), window = A.size() - B = 0.

It means that cur should always be 0. However, in your for loop, cur will always contain one value (A[i]).

To fix the problem, we can add an if statement after calculating the size of window.

int window=A.size()-B;
if (window == 0) {
    return sum;
}

CodePudding user response：

Sliding window is not applicable here.

Since the input contains both positive and negative elements, when you move the j (or even the i) pointer, you are not guaranteed if the cur (current window sum) that you calculate is going to include the correct elements to give you the right answer. In other words, you end up removing incorrect elements from your current window, leading to a wrong answer.