LeetCode 53. Maximum Subarray

Question

• https://leetcode.com/problems/maximum-subarray/

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

A subarray is a contiguous part of an array.

Code

import kotlin.math.max

class Solution {
    fun maxSubArray(nums: IntArray): Int {
        val ns = nums.toMutableList()
        var max = ns[0]
        for (i in 1..ns.lastIndex) {
            ns[i] = max(ns[i - 1] + ns[i], ns[i])
            max = max(ns[i], max)
        }
        return max
    }
}

単純に全探索する方法しか思いつかなかったが、すべてのsubarrayについて調べ上げようとすると2重forで探索することになるので時間計算量が$O(n^2)$となってしまう

Maximum subarrayについて調べてみると、「Maximum subarray Problem」というwikipediaがあり、有名なアルゴリズムとして取り扱われている問題で、どうやら日本語では、「最大部分配列問題」としてすでに取り扱われていることがわかる。

またその解き方として、Kadane's Algorithm(DPの一つ、$O(n)$)、分割統治法($O(log n)$)として紹介されることが多い。

Kadane's Algorithm は、現在位置をiとしたとき一つ前の位置(i-1)に過去の計算結果を累積させながら、都度現在位置の整数のとの和で最大値を更新する動的計画法の一種である。
以下は、[-2,1,-3,4,-1,2,1,-5,4]が与えられたときのトレースの様子をまとめたものだ。

分割統治法での解放はまたの機会としたい

Profile

• Runtime: 572 ms
• Memory Usage: 60.3 MB

Submission

• https://leetcode.com/submissions/detail/593991630/

Reference

• https://yottagin.com/?p=9876
• https://zenn.dev/ike_pon/articles/d709eaf7ba5255a22b1d
• https://zenn.dev/esaka/scraps/eacfd8700c0c53