{"id":35076,"date":"2024-11-01T09:35:17","date_gmt":"2024-11-01T09:35:17","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=35076"},"modified":"2024-11-01T12:46:28","modified_gmt":"2024-11-01T12:46:28","slug":"%ec%bd%94%ed%8b%80%eb%a6%b0-coding-test-course-finding-the-sum-of-consecutive-numbers","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/35076\/","title":{"rendered":"Kotlin Coding Test Course, Finding the Sum of Consecutive Numbers"},"content":{"rendered":"

<\/p>\n

\n

Problem Description<\/h2>\n

\n Given an integer array arr<\/code>, this is a problem of finding the maximum sum of a contiguous subarray.
\n In other words, you need to determine what the largest sum is when adding up a few consecutive numbers from arr<\/code>.
\n This problem is one of the frequently asked coding test questions and can be solved using Kadane’s algorithm.\n <\/p>\n

Problem Example<\/h2>\n

Input<\/h3>\n
[2, -1, 3, 4, -2, 1, -5, 4]<\/code><\/pre>\n
Output<\/h3>\n
10<\/code><\/pre>\n
Explanation: The sum of the contiguous subarray [3, 4, -2, 1] is the maximum at 10.<\/p>\n
Approach to the Problem<\/h2>\n
\n            Since this problem requires finding the sum of a contiguous subarray, the key is how to set the range.
\n            That is, while you can approach this by fixing starting and ending points and summing all elements in between,
\n            this method is inefficient. Instead, you can solve it in O(n) time complexity using Kadane’s algorithm.\n        <\/p>\n
Kadane’s Algorithm<\/h3>\n
\n            Kadane’s algorithm works by updating the maximum sum of the contiguous subarray so far by comparing it to the current position’s value.
\n            The specific steps are as follows:\n        <\/p>\n
    \n
  1. Initialize the variables maxSoFar<\/code> and maxEndingHere<\/code>. Both can be initialized to 0 or the first element of the array.<\/li>\n
  2. Traverse the array and add the current value arr[i]<\/code> to maxEndingHere<\/code>.<\/li>\n
  3. If maxEndingHere<\/code> is greater than maxSoFar<\/code>, update maxSoFar<\/code>.<\/li>\n
  4. If maxEndingHere<\/code> becomes less than 0, reset it to 0 to start a new contiguous sum.<\/li>\n<\/ol>\n
    \n            This method can find the maximum sum in O(n) time, regardless of the array size.\n        <\/p>\n
    Kotlin Code Implementation<\/h2>\n
    \n            Below is the code that implements the above algorithm in Kotlin:\n        <\/p>\n
    \nfun maxSubArraySum(arr: IntArray): Int {\n    var maxSoFar = arr[0]\n    var maxEndingHere = arr[0]\n\n    for (i in 1 until arr.size) {\n        maxEndingHere = Math.max(arr[i], maxEndingHere + arr[i])\n        maxSoFar = Math.max(maxSoFar, maxEndingHere)\n    }\n\n    return maxSoFar\n}\n\nfun main() {\n    val arr = intArrayOf(2, -1, 3, 4, -2, 1, -5, 4)\n    val result = maxSubArraySum(arr)\n    println(\"Maximum contiguous sum: $result\")\n}\n        <\/code><\/pre>\n
    The above code defines a function maxSubArraySum<\/code> that calculates the maximum contiguous sum from a given integer array.<\/p>\n
    Time Complexity Analysis<\/h2>\n
    \n            Since Kadane’s algorithm derives results through a single traversal of the array, its time complexity is O(n).
    \n            Therefore, increasing the size of the array does not significantly affect performance. The space complexity is O(1) and is very efficient as it does not use any additional data structures.\n        <\/p>\n
    Conclusion<\/h2>\n
    \n            The problem of finding contiguous sums is a frequently encountered issue in algorithm problem solving,
    \n            and can be efficiently solved through Kadane’s algorithm. This allows you to learn the basics of Kotlin syntax and algorithm design at the same time.
    \n            Since this is a problem that often appears in coding tests, practice it to be able to implement it naturally.\n        <\/p>\n
    Additional Practice Problems<\/h2>\n
    Try additional practice with the following modified problems:<\/p>\n