{"id":6408,"date":"2017-05-30T04:00:38","date_gmt":"2017-05-30T04:00:38","guid":{"rendered":"https:\/\/assignment.essayshark.com\/blog\/?p=6408"},"modified":"2023-01-09T13:05:28","modified_gmt":"2023-01-09T13:05:28","slug":"maximum-subarray-problem","status":"publish","type":"post","link":"https:\/\/assignmentshark.com\/blog\/maximum-subarray-problem\/","title":{"rendered":"Maximum Subarray Problem"},"content":{"rendered":"

In computer science, the maximum subarray problem is the task of finding the contiguous subarray within a one-dimensional array of numbers which has the largest sum. For example, for the sequence of values \u22122, 1, \u22123, 4, \u22121, 2, 1, \u22125, and 4, the contiguous subarray with the largest sum is 4, \u22121, 2, 1, with sum 6. (wikipedia.org, 2007).<\/p>\n

To solve this problem, we will use Kadane\u2019s Algorithm. It\u2019s essence is in the consistent checking of all positive integers in the array, searching for the contiguous segments and tracking their sums. Every time we get a positive sum we compare it with the current maximum sum, and if it\u2019s bigger, we consider the current sum to be maximal.<\/p>\n

\"\"<\/a><\/p>\n

\"\"<\/a><\/p>\n

\"\"<\/a><\/p>\n

\"\"<\/a><\/p>\n

\"\"<\/a><\/p>\n

\"\"<\/a><\/p>\n

\"\"<\/a><\/p>\n

\"\"<\/a><\/p>\n

\"\"<\/a><\/p>\n

\"\"<\/a><\/p>\n

\"\"<\/a><\/p>\n

\"\"<\/a><\/p>\n

\"\"<\/a><\/p>\n

Java implementation:<\/p>\n

[code language=”java”]
\npublic class Kadane {<\/p>\n

\tpublic static void main(String[] args) {
\n\t\tint[] array = { 2, -4, -6, -2, -8, -2, 1, 6, 3, 6 };<\/p>\n

\t\tsearchMaxSub(array);
\n\t}<\/p>\n

\tpublic static void searchMaxSub(int[] inArr) {<\/p>\n

\t\tint maxStartInd = 0;
\n\t\tint maxEndInd = 0;
\n\t\tint maxSum = Integer.MIN_VALUE;<\/p>\n

\t\tint aggregateSum = 0;
\n\t\tint tempMaxInd = 0;<\/p>\n

\t\tfor (int currInd = 0; currInd < inArr.length; currInd++) { int arrayItem = inArr[currInd]; aggregateSum += arrayItem; if (aggregateSum>maxSum) {
\n\t\t\t\tmaxSum = aggregateSum;
\n\t\t\t\tmaxStartInd = tempMaxInd;
\n\t\t\t\tmaxEndInd = currInd;
\n\t\t\t}
\n\t\t\telse if (aggregateSum<0) {
\n\t\t\t\ttempMaxInd = currInd + 1;
\n\t\t\t\taggregateSum = 0;
\n\t\t\t}
\n\t\t}<\/p>\n

\t\tSystem.out.println("Max sum : " + maxSum);
\n\t\tSystem.out.println("Max start index : " + maxStartInd);
\n\t\tSystem.out.println("Max end index : " + maxEndInd);
\n\t}<\/p>\n

}
\n[\/code]<\/p>\n

Computer Science Assignments Assistance 24\/7<\/h2>\n

Check out the new sample created by our experienced programming specialists. The sample that gives you a maximum subarray problem solved can help you deal with your own assignment or simply inspire you to work harder and find the solution to your task. We also advise you to check other samples at our blog, for example, one of the summation examples<\/a>, since you never know which one will help you to solve the task or inspire you to try a little bit harder. Don\u2019t worry, however, if you still have no idea how to do this task \u2013 you have a team of professionals to provide computer science assignments help<\/a> for you.<\/em><\/p>\n

All you need to get assignment help<\/a> is fill in the order form in the upper right corner and upload the files that are crucial for your assignment. Also, don\u2019t forget to specify whether your assignment has to be based upon a specific research, theory or method. After that, you will be asked to choose an expert you liked the most from those who have placed their bids under your order. You can always chat with your expert and ask any questions you have during the working process, and you will be asked to pay only after you receive a maximum subarray problem solved the way you needed it to be solved.<\/em><\/p><\/blockquote>\n","protected":false},"excerpt":{"rendered":"

In computer science, the maximum subarray problem is the task of finding the contiguous subarray within a one-dimensional array of numbers which has the largest sum. For example, for the sequence of values \u22122, 1, \u22123, 4, \u22121, 2, 1, \u22125, and 4, the contiguous subarray with the largest sum is 4, \u22121, 2, 1, […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[53,35],"tags":[],"class_list":["post-6408","post","type-post","status-publish","format-standard","hentry","category-it","category-samples"],"_links":{"self":[{"href":"https:\/\/assignmentshark.com\/blog\/wp-json\/wp\/v2\/posts\/6408","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/assignmentshark.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/assignmentshark.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/assignmentshark.com\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/assignmentshark.com\/blog\/wp-json\/wp\/v2\/comments?post=6408"}],"version-history":[{"count":8,"href":"https:\/\/assignmentshark.com\/blog\/wp-json\/wp\/v2\/posts\/6408\/revisions"}],"predecessor-version":[{"id":13461,"href":"https:\/\/assignmentshark.com\/blog\/wp-json\/wp\/v2\/posts\/6408\/revisions\/13461"}],"wp:attachment":[{"href":"https:\/\/assignmentshark.com\/blog\/wp-json\/wp\/v2\/media?parent=6408"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/assignmentshark.com\/blog\/wp-json\/wp\/v2\/categories?post=6408"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/assignmentshark.com\/blog\/wp-json\/wp\/v2\/tags?post=6408"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}