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.
相同的链接是
this
.
我编写了以下代码,使用这种方法来查找大小为的子阵列的最小连续和
total array size-B
使用滑动窗口并从总和中减去该总和,以获得所需的最大总和:
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;
}
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
我做了一些小改动,首先在一个单独的循环中计算第一个窗口和,然后将其指定为最小值,然后执行其余的过程,结果成功了。工作代码如下:
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;
}
请告诉我第一个代码哪里错了。我试了很多次,但自己找不到。
