[LeetCode] Maximum Subarray

[LeetCode] Maximum Subarray

 

1. 문제 : Link

하위 array 중 합의 최대값 찾는 문제

 

2. 풀이

array문제 유형에 있길래 dp 생각도 못했는데 dp 문제여따...

 

3. 코드

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        dp = [num for num in nums]
        for i in range(1, len(nums)):
            dp[i] = max(dp[i-1]+nums[i], nums[i])

        return max(dp)

 

class Solution {
public int maxSubArray(int[] nums) {
    int[] dp = new int[nums.length];
    for(int i=0; i<nums.length; i++){
        dp[i] = nums[i];
    }

    for(int i=1; i<nums.length; i++){
        dp[i] = Math.max(dp[i-1] + nums[i], nums[i]);
    }

    int max = Integer.MIN_VALUE;
    for(int i=0; i<nums.length; i++){
        if(dp[i] > max) max = dp[i];
    }

    return max;
    }
}