Hello! In this lecture, we will cover one of the algorithm problems using Python, Finding the Maximum Sum of Continuous Elements<\/strong>. This problem can be approached in various ways and is very useful for studying algorithms. We will explain the necessary basic theories and the solution process in detail.<\/p>\n Given an integer array Output the maximum sum of If we calculate the sum of 3 continuous elements in the given array, the largest value is To solve this problem, we need an algorithm that can calculate continuous sums. If we simply iterate through the array and sum all One useful technique to solve this problem is the Sliding Window<\/strong>. The sliding window is a method to quickly calculate a continuous subarray of a specific size within a given array or list. By using this technique, we can reduce the time complexity to Now, let’s implement this algorithm in Python. Here is an implementation using the sliding window:<\/p>\n Let\u2019s take a detailed look at each part of the code:<\/p>\nProblem Description<\/h2>\n
arr<\/code>, write an algorithm to maximize the sum of k<\/code> continuous elements within this array. The length of the array is given as n<\/code>, and k<\/code> is an integer from 1 to n<\/code>, inclusive. In other words, we need to calculate the sum of k<\/code> continuous elements in the array and return the maximum value of this sum.<\/p>\nInput<\/h3>\n
\n
n<\/code> (1 \u2264 n \u2264 100,000)<\/li>\narr<\/code> consisting of n<\/code> integers (-109<\/sup> \u2264 arri<\/sub> \u2264 109<\/sup>)<\/li>\nk<\/code> (1 \u2264 k \u2264 n)<\/li>\n<\/ul>\nOutput<\/h3>\n
k<\/code> continuous elements.<\/p>\nExample Input<\/h3>\n
5\n1 2 3 4 5\n3<\/pre>\n
Example Output<\/h3>\n
12<\/pre>\n
Explanation<\/h3>\n
3+4+5=12<\/code>.<\/p>\n<\/div>\nSolution Process<\/h2>\n
k<\/code> continuous elements to find the maximum, the time complexity would be O(n*k)<\/code>, which is not feasible if n<\/code> is 100,000. Therefore, we need to solve it in a more efficient way.<\/p>\nSliding Window Technique<\/h3>\n
O(n)<\/code>.<\/p>\nAlgorithm Explanation<\/h3>\n
\n
k<\/code> elements and set it as the current maximum sum.<\/li>\nk<\/code> elements by removing one element and adding a newly added element to update the sum.<\/li>\nImplementation Code<\/h3>\n
\ndef max_sum_k_elements(n, arr, k):\n # Initial window sum\n current_sum = sum(arr[:k])\n max_sum = current_sum\n\n # Use sliding window to explore the rest of the elements\n for i in range(k, n):\n current_sum += arr[i] - arr[i - k]\n max_sum = max(max_sum, current_sum)\n\n return max_sum\n\n# Input handling\nn = int(input())\narr = list(map(int, input().split()))\nk = int(input())\n\n# Output the maximum continuous sum\nprint(max_sum_k_elements(n, arr, k))<\/pre>\n
Code Explanation<\/h3>\n
\n
def max_sum_k_elements(n, arr, k):<\/code> – Function declaration that uses the input array and k<\/code> to calculate the maximum sum.<\/li>\ncurrent_sum = sum(arr[:k])<\/code> – Calculates the sum of the initial window.<\/li>\nmax_sum = current_sum<\/code> – Initializes the current maximum sum.<\/li>\nfor i in range(k, n):<\/code> – Loops from k<\/code> to n<\/code> for the sliding window.<\/li>\ncurrent_sum += arr[i] - arr[i - k]<\/code> – Includes the new element and subtracts the excluded element to update the current sum.<\/li>\nmax_sum = max(max_sum, current_sum)<\/code> – Updates the maximum sum.<\/li>\nreturn max_sum<\/code> – Returns the final maximum sum.<\/li>\n<\/ul>\nConclusion<\/h3>\n