Finding the submatrix with the maximum sumFind Missing Numbers in an int listHackerEarth: Find array index...
Is a debit card dangerous for an account with low balance and no overdraft protection?
Difference between thick vs thin front suspension?
How to apply float precision (type specifier) in a conditional f-string?
Can we use the stored gravitational potential energy of a building to produce power?
How would a Dictatorship make a country more successful?
Eww, those bytes are gross
Why does a metal block make a shrill sound but not a wooden block upon hammering?
Disable the ">" operator in Rstudio linux terminal
Solving Fredholm Equation of the second kind
How do you funnel food off a cutting board?
Using only 1s, make 29 with the minimum number of digits
Does fast page mode apply to ROM?
Why zero tolerance on nudity in space?
Why are the books in the Game of Thrones citadel library shelved spine inwards?
A minimum of two personnel "are" or "is"?
Strange Sign on Lab Door
Would these multi-classing house rules cause unintended problems?
Can a dragon be stuck looking like a human?
What creature do these Alchemical Humonculus actions target?
Why do members of Congress in committee hearings ask witnesses the same question multiple times?
Is there any differences between "Gucken" and "Schauen"?
How to tag distinct options/entities without giving any an implicit priority or suggested order?
Dilemma of explaining to interviewer that he is the reason for declining second interview
Why did other German political parties disband so fast when Hitler was appointed chancellor?
Finding the submatrix with the maximum sum
Find Missing Numbers in an int listHackerEarth: Find array index with cumulative sum till there matching a given targetFind the contiguous subarray within an array (containing at least one number) which has the largest sumFinding longest common prefixTo the right, to the left, now rotateComputing sum on column + sum on row + sum on each diagonalmo algorithm for summing the subarrayMaximum sub array sum equal to kCodility: MaxZeroProduct - complexity issuesSubarray Sum Equals K
$begingroup$
Given an arbitrary $N times N$ matrix, find the maximum sum submatrix. This particular approach uses the Kadane's algorithm. What could be improved both in terms of algorithm and code style?
def read_matrix_from_input():
return [[int(s) for s in input().split(" ")] for row in range(int(input()))]
def max_subarray_sum(array):
max_sum = current_sum = array[0]
for number in array[1:]:
current_sum = max(current_sum + number, number)
max_sum = max(max_sum, current_sum)
return max_sum
def max_submatrix_sum(row_major_matrix):
column_major_matrix = list(map(list, zip(*row_major_matrix)))
num_columns = len(column_major_matrix)
num_rows = len(column_major_matrix[0])
max_sum = column_major_matrix[0][0]
for left_offset in range(num_columns):
partial_sums = [0] * num_rows
for right_column in column_major_matrix[left_offset:]:
partial_sums = [partial_sums[row] + number for row, number in enumerate(right_column)]
max_sum = max(max_sum, max_subarray_sum(partial_sums))
return max_sum
if __name__ == "__main__":
print(max_submatrix_sum(read_matrix_from_input()))
python algorithm python-3.x
edited 10 hours ago
Graipher
25.2k53687
asked yesterday
Inter VeridiumInter Veridium
305
$endgroup$
add a comment |
$begingroup$
Given an arbitrary $N times N$ matrix, find the maximum sum submatrix. This particular approach uses the Kadane's algorithm. What could be improved both in terms of algorithm and code style?
def read_matrix_from_input():
return [[int(s) for s in input().split(" ")] for row in range(int(input()))]
def max_subarray_sum(array):
max_sum = current_sum = array[0]
for number in array[1:]:
current_sum = max(current_sum + number, number)
max_sum = max(max_sum, current_sum)
return max_sum
def max_submatrix_sum(row_major_matrix):
column_major_matrix = list(map(list, zip(*row_major_matrix)))
num_columns = len(column_major_matrix)
num_rows = len(column_major_matrix[0])
max_sum = column_major_matrix[0][0]
for left_offset in range(num_columns):
partial_sums = [0] * num_rows
for right_column in column_major_matrix[left_offset:]:
partial_sums = [partial_sums[row] + number for row, number in enumerate(right_column)]
max_sum = max(max_sum, max_subarray_sum(partial_sums))
return max_sum
if __name__ == "__main__":
print(max_submatrix_sum(read_matrix_from_input()))
python algorithm python-3.x
edited 10 hours ago
Graipher
25.2k53687
asked yesterday
Inter VeridiumInter Veridium
305
$endgroup$
add a comment |
$begingroup$
Given an arbitrary $N times N$ matrix, find the maximum sum submatrix. This particular approach uses the Kadane's algorithm. What could be improved both in terms of algorithm and code style?
def read_matrix_from_input():
return [[int(s) for s in input().split(" ")] for row in range(int(input()))]
def max_subarray_sum(array):
max_sum = current_sum = array[0]
for number in array[1:]:
current_sum = max(current_sum + number, number)
max_sum = max(max_sum, current_sum)
return max_sum
def max_submatrix_sum(row_major_matrix):
column_major_matrix = list(map(list, zip(*row_major_matrix)))
num_columns = len(column_major_matrix)
num_rows = len(column_major_matrix[0])
max_sum = column_major_matrix[0][0]
for left_offset in range(num_columns):
partial_sums = [0] * num_rows
for right_column in column_major_matrix[left_offset:]:
partial_sums = [partial_sums[row] + number for row, number in enumerate(right_column)]
max_sum = max(max_sum, max_subarray_sum(partial_sums))
return max_sum
if __name__ == "__main__":
print(max_submatrix_sum(read_matrix_from_input()))
python algorithm python-3.x
edited 10 hours ago
Graipher
25.2k53687
asked yesterday
Inter VeridiumInter Veridium
305
$endgroup$
Given an arbitrary $N times N$ matrix, find the maximum sum submatrix. This particular approach uses the Kadane's algorithm. What could be improved both in terms of algorithm and code style?
def read_matrix_from_input():
return [[int(s) for s in input().split(" ")] for row in range(int(input()))]
def max_subarray_sum(array):
max_sum = current_sum = array[0]
for number in array[1:]:
current_sum = max(current_sum + number, number)
max_sum = max(max_sum, current_sum)
return max_sum
def max_submatrix_sum(row_major_matrix):
column_major_matrix = list(map(list, zip(*row_major_matrix)))
num_columns = len(column_major_matrix)
num_rows = len(column_major_matrix[0])
max_sum = column_major_matrix[0][0]
for left_offset in range(num_columns):
partial_sums = [0] * num_rows
for right_column in column_major_matrix[left_offset:]:
partial_sums = [partial_sums[row] + number for row, number in enumerate(right_column)]
max_sum = max(max_sum, max_subarray_sum(partial_sums))
return max_sum
if __name__ == "__main__":
print(max_submatrix_sum(read_matrix_from_input()))
python algorithm python-3.x
python algorithm python-3.x
edited 10 hours ago
Graipher
25.2k53687
asked yesterday
Inter VeridiumInter Veridium
305
edited 10 hours ago
Graipher
25.2k53687
asked yesterday
Inter VeridiumInter Veridium
305
edited 10 hours ago
Graipher
25.2k53687
edited 10 hours ago
Graipher
25.2k53687
edited 10 hours ago
Graipher
25.2k53687
25.2k53687
asked yesterday
Inter VeridiumInter Veridium
305
asked yesterday
Inter VeridiumInter Veridium
305
asked yesterday
Inter VeridiumInter Veridium
305
305
add a comment |
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.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "196"
};
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: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
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%2fcodereview.stackexchange.com%2fquestions%2f214487%2ffinding-the-submatrix-with-the-maximum-sum%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 Code Review 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%2fcodereview.stackexchange.com%2fquestions%2f214487%2ffinding-the-submatrix-with-the-maximum-sum%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
