Mixing
How to check if sum of some contiguous subarray is equal to N?
So say I have a list sequences such as this.
I want to remove all sequences where its total sum = N and/or it has a contiguous subarray with sum = N.
For example, if N = 4, then (1,1,2) is not valid since its total is 4. (1,1,3) is also not valid since the (1,3) is also 4. (1,3,1) is also not valid for the same reason.
lst = [
(1,1,1), (1,1,2), (1,1,3),
(1,2,1), (1,2,2), (1,2,3),
(1,3,1), (1,3,2), (1,3,3),
(2,1,1), (2,1,2), (2,1,3),
(2,2,1), (2,2,2), (2,2,3),
(2,3,1), (2,3,2), (2,3,3),
(3,1,1), (3,1,2), (3,1,3),
(3,2,1), (3,2,2), (3,2,3),
(3,3,1), (3,3,2), (3,3,3)
]
What are some ways to do this?
I'm currently trying to see if I'm able to remove sequences whose total is not necessarily a multiple of N but not its contiguous subarrays, but I'm unsuccessful
for elements in list(product(range(1,n), repeat=n-1)):
lst.append(elements)
for val in lst:
if np.cumsum(val).any() %n != 0:
lst2.append(val) # append value to a filtered list
python python-3.x
edited Nov 19 '18 at 20:15
eozd
8941515
asked Nov 19 '18 at 18:19
ThegreatfooThegreatfoo
385
add a comment |
So say I have a list sequences such as this.
I want to remove all sequences where its total sum = N and/or it has a contiguous subarray with sum = N.
For example, if N = 4, then (1,1,2) is not valid since its total is 4. (1,1,3) is also not valid since the (1,3) is also 4. (1,3,1) is also not valid for the same reason.
lst = [
(1,1,1), (1,1,2), (1,1,3),
(1,2,1), (1,2,2), (1,2,3),
(1,3,1), (1,3,2), (1,3,3),
(2,1,1), (2,1,2), (2,1,3),
(2,2,1), (2,2,2), (2,2,3),
(2,3,1), (2,3,2), (2,3,3),
(3,1,1), (3,1,2), (3,1,3),
(3,2,1), (3,2,2), (3,2,3),
(3,3,1), (3,3,2), (3,3,3)
]
What are some ways to do this?
I'm currently trying to see if I'm able to remove sequences whose total is not necessarily a multiple of N but not its contiguous subarrays, but I'm unsuccessful
for elements in list(product(range(1,n), repeat=n-1)):
lst.append(elements)
for val in lst:
if np.cumsum(val).any() %n != 0:
lst2.append(val) # append value to a filtered list
python python-3.x
edited Nov 19 '18 at 20:15
eozd
8941515
asked Nov 19 '18 at 18:19
ThegreatfooThegreatfoo
385
Is it guaranteed that the numbers in your little sequences like (1,1,3) are nonnegative? Also, what is the maximum length of these "little" sequences?
– eozd
Nov 19 '18 at 18:52
Yes, they are guaranteed to be negative and the maximum length is N-1.
– Thegreatfoo
Nov 19 '18 at 19:05
You mean they are guaranteed to be nonnegative? If so, there is a very efficient linear time solution given by Neb. @Thegreatfoo So, I think it is also worth mentioning in the question how big N can be and what are the negativity conditions on the elements.
– eozd
Nov 19 '18 at 19:07
*Non-negative, my mistake. Also the range of N in this case is 2 <= n <= 1000)
– Thegreatfoo
Nov 19 '18 at 19:13
add a comment |
So say I have a list sequences such as this.
I want to remove all sequences where its total sum = N and/or it has a contiguous subarray with sum = N.
For example, if N = 4, then (1,1,2) is not valid since its total is 4. (1,1,3) is also not valid since the (1,3) is also 4. (1,3,1) is also not valid for the same reason.
lst = [
(1,1,1), (1,1,2), (1,1,3),
(1,2,1), (1,2,2), (1,2,3),
(1,3,1), (1,3,2), (1,3,3),
(2,1,1), (2,1,2), (2,1,3),
(2,2,1), (2,2,2), (2,2,3),
(2,3,1), (2,3,2), (2,3,3),
(3,1,1), (3,1,2), (3,1,3),
(3,2,1), (3,2,2), (3,2,3),
(3,3,1), (3,3,2), (3,3,3)
]
What are some ways to do this?
I'm currently trying to see if I'm able to remove sequences whose total is not necessarily a multiple of N but not its contiguous subarrays, but I'm unsuccessful
for elements in list(product(range(1,n), repeat=n-1)):
lst.append(elements)
for val in lst:
if np.cumsum(val).any() %n != 0:
lst2.append(val) # append value to a filtered list
python python-3.x
edited Nov 19 '18 at 20:15
eozd
8941515
asked Nov 19 '18 at 18:19
ThegreatfooThegreatfoo
385
So say I have a list sequences such as this.
I want to remove all sequences where its total sum = N and/or it has a contiguous subarray with sum = N.
For example, if N = 4, then (1,1,2) is not valid since its total is 4. (1,1,3) is also not valid since the (1,3) is also 4. (1,3,1) is also not valid for the same reason.
lst = [
(1,1,1), (1,1,2), (1,1,3),
(1,2,1), (1,2,2), (1,2,3),
(1,3,1), (1,3,2), (1,3,3),
(2,1,1), (2,1,2), (2,1,3),
(2,2,1), (2,2,2), (2,2,3),
(2,3,1), (2,3,2), (2,3,3),
(3,1,1), (3,1,2), (3,1,3),
(3,2,1), (3,2,2), (3,2,3),
(3,3,1), (3,3,2), (3,3,3)
]
What are some ways to do this?
I'm currently trying to see if I'm able to remove sequences whose total is not necessarily a multiple of N but not its contiguous subarrays, but I'm unsuccessful
for elements in list(product(range(1,n), repeat=n-1)):
lst.append(elements)
for val in lst:
if np.cumsum(val).any() %n != 0:
lst2.append(val) # append value to a filtered list
python python-3.x
python python-3.x
edited Nov 19 '18 at 20:15
eozd
8941515
asked Nov 19 '18 at 18:19
ThegreatfooThegreatfoo
385
edited Nov 19 '18 at 20:15
eozd
8941515
asked Nov 19 '18 at 18:19
ThegreatfooThegreatfoo
385
edited Nov 19 '18 at 20:15
eozd
8941515
edited Nov 19 '18 at 20:15
eozd
8941515
edited Nov 19 '18 at 20:15
eozd
8941515
8941515
asked Nov 19 '18 at 18:19
ThegreatfooThegreatfoo
385
asked Nov 19 '18 at 18:19
ThegreatfooThegreatfoo
385
asked Nov 19 '18 at 18:19
ThegreatfooThegreatfoo
385
385
Is it guaranteed that the numbers in your little sequences like (1,1,3) are nonnegative? Also, what is the maximum length of these "little" sequences?
– eozd
Nov 19 '18 at 18:52
Yes, they are guaranteed to be negative and the maximum length is N-1.
– Thegreatfoo
Nov 19 '18 at 19:05
You mean they are guaranteed to be nonnegative? If so, there is a very efficient linear time solution given by Neb. @Thegreatfoo So, I think it is also worth mentioning in the question how big N can be and what are the negativity conditions on the elements.
– eozd
Nov 19 '18 at 19:07
*Non-negative, my mistake. Also the range of N in this case is 2 <= n <= 1000)
– Thegreatfoo
Nov 19 '18 at 19:13
add a comment |
Is it guaranteed that the numbers in your little sequences like (1,1,3) are nonnegative? Also, what is the maximum length of these "little" sequences?
– eozd
Nov 19 '18 at 18:52
Yes, they are guaranteed to be negative and the maximum length is N-1.
– Thegreatfoo
Nov 19 '18 at 19:05
You mean they are guaranteed to be nonnegative? If so, there is a very efficient linear time solution given by Neb. @Thegreatfoo So, I think it is also worth mentioning in the question how big N can be and what are the negativity conditions on the elements.
– eozd
Nov 19 '18 at 19:07
*Non-negative, my mistake. Also the range of N in this case is 2 <= n <= 1000)
– Thegreatfoo
Nov 19 '18 at 19:13
Is it guaranteed that the numbers in your little sequences like (1,1,3) are nonnegative? Also, what is the maximum length of these "little" sequences?
– eozd
Nov 19 '18 at 18:52
Is it guaranteed that the numbers in your little sequences like (1,1,3) are nonnegative? Also, what is the maximum length of these "little" sequences?
– eozd
Nov 19 '18 at 18:52
Yes, they are guaranteed to be negative and the maximum length is N-1.
– Thegreatfoo
Nov 19 '18 at 19:05
Yes, they are guaranteed to be negative and the maximum length is N-1.
– Thegreatfoo
Nov 19 '18 at 19:05
You mean they are guaranteed to be nonnegative? If so, there is a very efficient linear time solution given by Neb. @Thegreatfoo So, I think it is also worth mentioning in the question how big N can be and what are the negativity conditions on the elements.
– eozd
Nov 19 '18 at 19:07
You mean they are guaranteed to be nonnegative? If so, there is a very efficient linear time solution given by Neb. @Thegreatfoo So, I think it is also worth mentioning in the question how big N can be and what are the negativity conditions on the elements.
– eozd
Nov 19 '18 at 19:07
*Non-negative, my mistake. Also the range of N in this case is 2 <= n <= 1000)
– Thegreatfoo
Nov 19 '18 at 19:13
*Non-negative, my mistake. Also the range of N in this case is 2 <= n <= 1000)
– Thegreatfoo
Nov 19 '18 at 19:13
add a comment |
2 Answers
2
active
oldest
votes
You can use itertools.combinations to generate all combinations of slice indices to test for sums of subsequences:
from itertools import combinations
[t for t in lst if not any(sum(t[l:h+1]) == 4 for l, h in combinations(range(len(t)), 2))]
This returns:
[(1, 1, 1), (1, 2, 3), (2, 3, 2), (2, 3, 3), (3, 2, 1), (3, 2, 3), (3, 3, 2), (3, 3, 3)]
answered Nov 19 '18 at 19:06
blhsingblhsing
28.7k41336
If max length isN-1, the OP may need it to generalize to anyN
– Brian Cohan
Nov 19 '18 at 19:16
1
Thank you, your solution worked!
– Thegreatfoo
Nov 19 '18 at 20:29
add a comment |
You can split your problem into two subproblems:
The elements in your list sum up to N. Then you can simply test:
if sum(myList) == N:
# do fancy stuff
The elements in your list do not sum up to N. In this case, there might be a subsequence that sum up to N. To find it, let's define two pointers,
landr. Their name stand forleftandrightand will define the boundaries of your subsequence. Then, the solution is the following:
r = 1
l = 0
while r <= len(myList):
sum_ = sum(myList[l:r])
if sum_ < 4:
r += 1
elif sum_ > 4:
l += 1
else:
# do fancy stuff and exit from the loop
break
It works as follows. First you initialize
landrso that you consider the subsequence consisting of only the first element ofmyList. Then, you sum the element of the subsequence and if the sum is lower than N, you enlarge the subsequence by adding1tor. If it is greater than N, then you restrict the subsequence by adding1tol.
Note thanks to eozd:
The above algorithm works only if the elemnent of the list are non-negative.
answered Nov 19 '18 at 18:58
NebNeb
1,246517
The second algorithm works only if the elements in the sequence are nonnegative. I think it is worth mentioning.
– eozd
Nov 19 '18 at 19:05
You are right, I assumed they were all non-negative because of the example given by the OP
– Neb
Nov 19 '18 at 19:06
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53380515%2fhow-to-check-if-sum-of-some-contiguous-subarray-is-equal-to-n%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
You can use itertools.combinations to generate all combinations of slice indices to test for sums of subsequences:
from itertools import combinations
[t for t in lst if not any(sum(t[l:h+1]) == 4 for l, h in combinations(range(len(t)), 2))]
This returns:
[(1, 1, 1), (1, 2, 3), (2, 3, 2), (2, 3, 3), (3, 2, 1), (3, 2, 3), (3, 3, 2), (3, 3, 3)]
answered Nov 19 '18 at 19:06
blhsingblhsing
28.7k41336
If max length isN-1, the OP may need it to generalize to anyN
– Brian Cohan
Nov 19 '18 at 19:16
1
Thank you, your solution worked!
– Thegreatfoo
Nov 19 '18 at 20:29
add a comment |
You can use itertools.combinations to generate all combinations of slice indices to test for sums of subsequences:
from itertools import combinations
[t for t in lst if not any(sum(t[l:h+1]) == 4 for l, h in combinations(range(len(t)), 2))]
This returns:
[(1, 1, 1), (1, 2, 3), (2, 3, 2), (2, 3, 3), (3, 2, 1), (3, 2, 3), (3, 3, 2), (3, 3, 3)]
answered Nov 19 '18 at 19:06
blhsingblhsing
28.7k41336
If max length isN-1, the OP may need it to generalize to anyN
– Brian Cohan
Nov 19 '18 at 19:16
1
Thank you, your solution worked!
– Thegreatfoo
Nov 19 '18 at 20:29
add a comment |
You can use itertools.combinations to generate all combinations of slice indices to test for sums of subsequences:
from itertools import combinations
[t for t in lst if not any(sum(t[l:h+1]) == 4 for l, h in combinations(range(len(t)), 2))]
This returns:
[(1, 1, 1), (1, 2, 3), (2, 3, 2), (2, 3, 3), (3, 2, 1), (3, 2, 3), (3, 3, 2), (3, 3, 3)]
answered Nov 19 '18 at 19:06
blhsingblhsing
28.7k41336
You can use itertools.combinations to generate all combinations of slice indices to test for sums of subsequences:
from itertools import combinations
[t for t in lst if not any(sum(t[l:h+1]) == 4 for l, h in combinations(range(len(t)), 2))]
This returns:
[(1, 1, 1), (1, 2, 3), (2, 3, 2), (2, 3, 3), (3, 2, 1), (3, 2, 3), (3, 3, 2), (3, 3, 3)]
answered Nov 19 '18 at 19:06
blhsingblhsing
28.7k41336
answered Nov 19 '18 at 19:06
blhsingblhsing
28.7k41336
answered Nov 19 '18 at 19:06
blhsingblhsing
28.7k41336
answered Nov 19 '18 at 19:06
blhsingblhsing
28.7k41336
28.7k41336
If max length isN-1, the OP may need it to generalize to anyN
– Brian Cohan
Nov 19 '18 at 19:16
1
Thank you, your solution worked!
– Thegreatfoo
Nov 19 '18 at 20:29
add a comment |
If max length isN-1, the OP may need it to generalize to anyN
– Brian Cohan
Nov 19 '18 at 19:16
1
Thank you, your solution worked!
– Thegreatfoo
Nov 19 '18 at 20:29
If max length is
N-1, the OP may need it to generalize to any N– Brian Cohan
Nov 19 '18 at 19:16
If max length is
N-1, the OP may need it to generalize to any N– Brian Cohan
Nov 19 '18 at 19:16
1
1
Thank you, your solution worked!
– Thegreatfoo
Nov 19 '18 at 20:29
Thank you, your solution worked!
– Thegreatfoo
Nov 19 '18 at 20:29
add a comment |
You can split your problem into two subproblems:
The elements in your list sum up to N. Then you can simply test:
if sum(myList) == N:
# do fancy stuff
The elements in your list do not sum up to N. In this case, there might be a subsequence that sum up to N. To find it, let's define two pointers,
landr. Their name stand forleftandrightand will define the boundaries of your subsequence. Then, the solution is the following:
r = 1
l = 0
while r <= len(myList):
sum_ = sum(myList[l:r])
if sum_ < 4:
r += 1
elif sum_ > 4:
l += 1
else:
# do fancy stuff and exit from the loop
break
It works as follows. First you initialize
landrso that you consider the subsequence consisting of only the first element ofmyList. Then, you sum the element of the subsequence and if the sum is lower than N, you enlarge the subsequence by adding1tor. If it is greater than N, then you restrict the subsequence by adding1tol.
Note thanks to eozd:
The above algorithm works only if the elemnent of the list are non-negative.
answered Nov 19 '18 at 18:58
NebNeb
1,246517
The second algorithm works only if the elements in the sequence are nonnegative. I think it is worth mentioning.
– eozd
Nov 19 '18 at 19:05
You are right, I assumed they were all non-negative because of the example given by the OP
– Neb
Nov 19 '18 at 19:06
add a comment |
You can split your problem into two subproblems:
The elements in your list sum up to N. Then you can simply test:
if sum(myList) == N:
# do fancy stuff
The elements in your list do not sum up to N. In this case, there might be a subsequence that sum up to N. To find it, let's define two pointers,
landr. Their name stand forleftandrightand will define the boundaries of your subsequence. Then, the solution is the following:
r = 1
l = 0
while r <= len(myList):
sum_ = sum(myList[l:r])
if sum_ < 4:
r += 1
elif sum_ > 4:
l += 1
else:
# do fancy stuff and exit from the loop
break
It works as follows. First you initialize
landrso that you consider the subsequence consisting of only the first element ofmyList. Then, you sum the element of the subsequence and if the sum is lower than N, you enlarge the subsequence by adding1tor. If it is greater than N, then you restrict the subsequence by adding1tol.
Note thanks to eozd:
The above algorithm works only if the elemnent of the list are non-negative.
answered Nov 19 '18 at 18:58
NebNeb
1,246517
The second algorithm works only if the elements in the sequence are nonnegative. I think it is worth mentioning.
– eozd
Nov 19 '18 at 19:05
You are right, I assumed they were all non-negative because of the example given by the OP
– Neb
Nov 19 '18 at 19:06
add a comment |
You can split your problem into two subproblems:
The elements in your list sum up to N. Then you can simply test:
if sum(myList) == N:
# do fancy stuff
The elements in your list do not sum up to N. In this case, there might be a subsequence that sum up to N. To find it, let's define two pointers,
landr. Their name stand forleftandrightand will define the boundaries of your subsequence. Then, the solution is the following:
r = 1
l = 0
while r <= len(myList):
sum_ = sum(myList[l:r])
if sum_ < 4:
r += 1
elif sum_ > 4:
l += 1
else:
# do fancy stuff and exit from the loop
break
It works as follows. First you initialize
landrso that you consider the subsequence consisting of only the first element ofmyList. Then, you sum the element of the subsequence and if the sum is lower than N, you enlarge the subsequence by adding1tor. If it is greater than N, then you restrict the subsequence by adding1tol.
Note thanks to eozd:
The above algorithm works only if the elemnent of the list are non-negative.
answered Nov 19 '18 at 18:58
NebNeb
1,246517
You can split your problem into two subproblems:
The elements in your list sum up to N. Then you can simply test:
if sum(myList) == N:
# do fancy stuff
The elements in your list do not sum up to N. In this case, there might be a subsequence that sum up to N. To find it, let's define two pointers,
landr. Their name stand forleftandrightand will define the boundaries of your subsequence. Then, the solution is the following:
r = 1
l = 0
while r <= len(myList):
sum_ = sum(myList[l:r])
if sum_ < 4:
r += 1
elif sum_ > 4:
l += 1
else:
# do fancy stuff and exit from the loop
break
It works as follows. First you initialize
landrso that you consider the subsequence consisting of only the first element ofmyList. Then, you sum the element of the subsequence and if the sum is lower than N, you enlarge the subsequence by adding1tor. If it is greater than N, then you restrict the subsequence by adding1tol.
Note thanks to eozd:
The above algorithm works only if the elemnent of the list are non-negative.
answered Nov 19 '18 at 18:58
NebNeb
1,246517
edited Nov 19 '18 at 19:07
answered Nov 19 '18 at 18:58
NebNeb
1,246517
answered Nov 19 '18 at 18:58
NebNeb
1,246517
answered Nov 19 '18 at 18:58
NebNeb
1,246517
1,246517
The second algorithm works only if the elements in the sequence are nonnegative. I think it is worth mentioning.
– eozd
Nov 19 '18 at 19:05
You are right, I assumed they were all non-negative because of the example given by the OP
– Neb
Nov 19 '18 at 19:06
add a comment |
The second algorithm works only if the elements in the sequence are nonnegative. I think it is worth mentioning.
– eozd
Nov 19 '18 at 19:05
You are right, I assumed they were all non-negative because of the example given by the OP
– Neb
Nov 19 '18 at 19:06
The second algorithm works only if the elements in the sequence are nonnegative. I think it is worth mentioning.
– eozd
Nov 19 '18 at 19:05
The second algorithm works only if the elements in the sequence are nonnegative. I think it is worth mentioning.
– eozd
Nov 19 '18 at 19:05
You are right, I assumed they were all non-negative because of the example given by the OP
– Neb
Nov 19 '18 at 19:06
You are right, I assumed they were all non-negative because of the example given by the OP
– Neb
Nov 19 '18 at 19:06
add a comment |
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53380515%2fhow-to-check-if-sum-of-some-contiguous-subarray-is-equal-to-n%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Is it guaranteed that the numbers in your little sequences like (1,1,3) are nonnegative? Also, what is the maximum length of these "little" sequences?
– eozd
Nov 19 '18 at 18:52
Yes, they are guaranteed to be negative and the maximum length is N-1.
– Thegreatfoo
Nov 19 '18 at 19:05
You mean they are guaranteed to be nonnegative? If so, there is a very efficient linear time solution given by Neb. @Thegreatfoo So, I think it is also worth mentioning in the question how big N can be and what are the negativity conditions on the elements.
– eozd
Nov 19 '18 at 19:07
*Non-negative, my mistake. Also the range of N in this case is 2 <= n <= 1000)
– Thegreatfoo
Nov 19 '18 at 19:13