Mixing
How can I find the max. sum of 'k' subarrays?
$begingroup$
I am preparing for a national programming competition and I encountered this problem.
It is as follows : -
You are given an array of length M. You are required to select K non-intersecting subarrays. The cost will be considered as the sum of all numbers in these subarrays divided by K . Your task is to maximize this cost.
You can select no subarrays (0) and the cost(C) will be ZERO IN THAT CASE!
If there are more than one solutions that contain the same cost, then select the one that contains the highest VALUE OF K.
You have to print the value of C and K
Array consists of positive as well as negative integers.
Here is my solution :-
I used Kadane's algorithm,
to find the longest subarray and printed K as 1 and the sum. It passed a few tests though : D
How can I efficiently solve this problem?
Do I have to apply Kadane's algorithm again and again?
Example-->
Subarray : 1 2 3 4 -100 -33330 -345 1 2 3 4 5
Here,we can choose, 2 subarrays:- {1,2,3,4} and {1,2,3,4,5},
our cost will be= ((10)+(15))/2=12.5
On the other hand, if we only choose 1 subarray, then the sum is 15/1=15(which is also the cost)
So, the best way is to choose only 1 subarray in this above example-case.:-)
programming
asked Jan 23 at 17:59
Karan GujarKaran Gujar
63
$endgroup$
add a comment |
$begingroup$
I am preparing for a national programming competition and I encountered this problem.
It is as follows : -
You are given an array of length M. You are required to select K non-intersecting subarrays. The cost will be considered as the sum of all numbers in these subarrays divided by K . Your task is to maximize this cost.
You can select no subarrays (0) and the cost(C) will be ZERO IN THAT CASE!
If there are more than one solutions that contain the same cost, then select the one that contains the highest VALUE OF K.
You have to print the value of C and K
Array consists of positive as well as negative integers.
Here is my solution :-
I used Kadane's algorithm,
to find the longest subarray and printed K as 1 and the sum. It passed a few tests though : D
How can I efficiently solve this problem?
Do I have to apply Kadane's algorithm again and again?
Example-->
Subarray : 1 2 3 4 -100 -33330 -345 1 2 3 4 5
Here,we can choose, 2 subarrays:- {1,2,3,4} and {1,2,3,4,5},
our cost will be= ((10)+(15))/2=12.5
On the other hand, if we only choose 1 subarray, then the sum is 15/1=15(which is also the cost)
So, the best way is to choose only 1 subarray in this above example-case.:-)
programming
asked Jan 23 at 17:59
Karan GujarKaran Gujar
63
$endgroup$
$begingroup$
'The cost will be considered as the sum of all numbers in these subarrays divided by K .' - could you elaborate? You get K sums, do you sum them after that? Do you take the max? Also you said you are supposed to take K subarrays, but at the same time you allow picking none.
$endgroup$
– lightxbulb
Jan 23 at 18:04
$begingroup$
Hi and Welcome to the Math.SE. If you want to pose nice questions, please consider the use of MathJax syntax in order to produce beautiful and beautifully formatted mathematical texts.
$endgroup$
– Daniele Tampieri
Jan 23 at 18:06
$begingroup$
@ lightxbulb explained above, more clearly ,now :-)
$endgroup$
– Karan Gujar
Jan 23 at 18:15
add a comment |
$begingroup$
I am preparing for a national programming competition and I encountered this problem.
It is as follows : -
You are given an array of length M. You are required to select K non-intersecting subarrays. The cost will be considered as the sum of all numbers in these subarrays divided by K . Your task is to maximize this cost.
You can select no subarrays (0) and the cost(C) will be ZERO IN THAT CASE!
If there are more than one solutions that contain the same cost, then select the one that contains the highest VALUE OF K.
You have to print the value of C and K
Array consists of positive as well as negative integers.
Here is my solution :-
I used Kadane's algorithm,
to find the longest subarray and printed K as 1 and the sum. It passed a few tests though : D
How can I efficiently solve this problem?
Do I have to apply Kadane's algorithm again and again?
Example-->
Subarray : 1 2 3 4 -100 -33330 -345 1 2 3 4 5
Here,we can choose, 2 subarrays:- {1,2,3,4} and {1,2,3,4,5},
our cost will be= ((10)+(15))/2=12.5
On the other hand, if we only choose 1 subarray, then the sum is 15/1=15(which is also the cost)
So, the best way is to choose only 1 subarray in this above example-case.:-)
programming
asked Jan 23 at 17:59
Karan GujarKaran Gujar
63
$endgroup$
I am preparing for a national programming competition and I encountered this problem.
It is as follows : -
You are given an array of length M. You are required to select K non-intersecting subarrays. The cost will be considered as the sum of all numbers in these subarrays divided by K . Your task is to maximize this cost.
You can select no subarrays (0) and the cost(C) will be ZERO IN THAT CASE!
If there are more than one solutions that contain the same cost, then select the one that contains the highest VALUE OF K.
You have to print the value of C and K
Array consists of positive as well as negative integers.
Here is my solution :-
I used Kadane's algorithm,
to find the longest subarray and printed K as 1 and the sum. It passed a few tests though : D
How can I efficiently solve this problem?
Do I have to apply Kadane's algorithm again and again?
Example-->
Subarray : 1 2 3 4 -100 -33330 -345 1 2 3 4 5
Here,we can choose, 2 subarrays:- {1,2,3,4} and {1,2,3,4,5},
our cost will be= ((10)+(15))/2=12.5
On the other hand, if we only choose 1 subarray, then the sum is 15/1=15(which is also the cost)
So, the best way is to choose only 1 subarray in this above example-case.:-)
programming
programming
asked Jan 23 at 17:59
Karan GujarKaran Gujar
63
asked Jan 23 at 17:59
Karan GujarKaran Gujar
63
edited Jan 23 at 18:15
Karan Gujar
asked Jan 23 at 17:59
Karan GujarKaran Gujar
63
asked Jan 23 at 17:59
Karan GujarKaran Gujar
63
asked Jan 23 at 17:59
Karan GujarKaran Gujar
63
63
$begingroup$
'The cost will be considered as the sum of all numbers in these subarrays divided by K .' - could you elaborate? You get K sums, do you sum them after that? Do you take the max? Also you said you are supposed to take K subarrays, but at the same time you allow picking none.
$endgroup$
– lightxbulb
Jan 23 at 18:04
$begingroup$
Hi and Welcome to the Math.SE. If you want to pose nice questions, please consider the use of MathJax syntax in order to produce beautiful and beautifully formatted mathematical texts.
$endgroup$
– Daniele Tampieri
Jan 23 at 18:06
$begingroup$
@ lightxbulb explained above, more clearly ,now :-)
$endgroup$
– Karan Gujar
Jan 23 at 18:15
add a comment |
$begingroup$
'The cost will be considered as the sum of all numbers in these subarrays divided by K .' - could you elaborate? You get K sums, do you sum them after that? Do you take the max? Also you said you are supposed to take K subarrays, but at the same time you allow picking none.
$endgroup$
– lightxbulb
Jan 23 at 18:04
$begingroup$
Hi and Welcome to the Math.SE. If you want to pose nice questions, please consider the use of MathJax syntax in order to produce beautiful and beautifully formatted mathematical texts.
$endgroup$
– Daniele Tampieri
Jan 23 at 18:06
$begingroup$
@ lightxbulb explained above, more clearly ,now :-)
$endgroup$
– Karan Gujar
Jan 23 at 18:15
$begingroup$
'The cost will be considered as the sum of all numbers in these subarrays divided by K .' - could you elaborate? You get K sums, do you sum them after that? Do you take the max? Also you said you are supposed to take K subarrays, but at the same time you allow picking none.
$endgroup$
– lightxbulb
Jan 23 at 18:04
$begingroup$
'The cost will be considered as the sum of all numbers in these subarrays divided by K .' - could you elaborate? You get K sums, do you sum them after that? Do you take the max? Also you said you are supposed to take K subarrays, but at the same time you allow picking none.
$endgroup$
– lightxbulb
Jan 23 at 18:04
$begingroup$
Hi and Welcome to the Math.SE. If you want to pose nice questions, please consider the use of MathJax syntax in order to produce beautiful and beautifully formatted mathematical texts.
$endgroup$
– Daniele Tampieri
Jan 23 at 18:06
$begingroup$
Hi and Welcome to the Math.SE. If you want to pose nice questions, please consider the use of MathJax syntax in order to produce beautiful and beautifully formatted mathematical texts.
$endgroup$
– Daniele Tampieri
Jan 23 at 18:06
$begingroup$
@ lightxbulb explained above, more clearly ,now :-)
$endgroup$
– Karan Gujar
Jan 23 at 18:15
$begingroup$
@ lightxbulb explained above, more clearly ,now :-)
$endgroup$
– Karan Gujar
Jan 23 at 18:15
add a comment |
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
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
},
noCode: 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%2fmath.stackexchange.com%2fquestions%2f3084835%2fhow-can-i-find-the-max-sum-of-k-subarrays%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Mathematics Stack Exchange!
- 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.
Use MathJax to format equations. MathJax reference.
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%2fmath.stackexchange.com%2fquestions%2f3084835%2fhow-can-i-find-the-max-sum-of-k-subarrays%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
$begingroup$
'The cost will be considered as the sum of all numbers in these subarrays divided by K .' - could you elaborate? You get K sums, do you sum them after that? Do you take the max? Also you said you are supposed to take K subarrays, but at the same time you allow picking none.
$endgroup$
– lightxbulb
Jan 23 at 18:04
$begingroup$
Hi and Welcome to the Math.SE. If you want to pose nice questions, please consider the use of MathJax syntax in order to produce beautiful and beautifully formatted mathematical texts.
$endgroup$
– Daniele Tampieri
Jan 23 at 18:06
$begingroup$
@ lightxbulb explained above, more clearly ,now :-)
$endgroup$
– Karan Gujar
Jan 23 at 18:15