FRTKL

53. Maximum Subarray (Easy)

Problem

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

  • 整数の配列 nums が与えられたとき、最大の和を持つ連続する部分配列(少なくとも1つの数を含む)を見つけ、その和を返す
    • input: [-2,1,-3,4,-1,2,1,-5,4]
    • output: 6

Solution

Go

func maxSubArray(nums []int) int {
    maxVal := max(nums...)
    sum := 0
    
    for _, num := range nums {
        sum += num
        
        if num > sum {
            sum = num
        }
        
        if sum > maxVal {
            maxVal = sum
        }
    }
    
    return maxVal
}


func max(nums ...int) int {
    if len(nums) == 0 {
        panic("funciton max() requires at least one argument.")
    }
    res := nums[0]
    for i := 0; i < len(nums); i++ {
        res = int(math.Max(float64(res), float64(nums[i])))
    }
    return res
}

PHP

class Solution {

    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function maxSubArray($nums) {
        $maxSum = max($nums);
        $targetNums = $nums;
        
        foreach ($nums as $num) {
            $sum = array_shift($targetNums);

            if (!$targetNums && ($maxSum < $sum)) {
                $maxSum = $sum;
            }

            foreach ($targetNums as $targetNum) {
                $sum += $targetNum;
                
                if ($maxSum < $sum) {
                    $maxSum = $sum;
                }
            }
        }
        
        return $maxSum;
    }
}

Impression

Written By Fukuaki TAKANO
fortkle icon

Engineering Manager at Connehito inc.
Please contact me via twitter. @fortkle