[파이썬 PYTHON · 자바 JAVA] LeetCode【Maximum Subarray】

Maximum Subarray - LeetCode

---

자바 코드

class Solution {
    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0]=nums[0];
        int ans = nums[0];
        for(int i=1;i<nums.length;i++){
            dp[i]=Math.max(dp[i-1]+nums[i],nums[i]);
            ans = Math.max(ans,dp[i]);
        }

        return ans;
    }
}

파이썬 코드

class Solution(object):
    def maxSubArray(self, nums):
        ans = nums[0]

        for i in range(1,len(nums)):
            dp.append(max(nums[i],dp[i-1]+nums[i]))
        
        return max(dp)

 

dp 문제였다.

 

dp 문제인지 모르고 한참 다른 방법으로 풀어보려고 했었다..

 

---

arr = [ -2, 1, -3, 4, -1, 2, 1, -5, 4 ]

 

dp[0] = -2

 

---

 

dp[1] 은

 

arr[0] + arr[1] (-2 + 1) 과 arr[1] ( 1 ) 중 큰 값을 고른다.

 

dp[1] = 1

 

---

dp[2] 는

 

arr[0] + arr[1] + arr[2] 와 arr[1] + arr[2] 와 arr[2] 중 큰 값을 고른다.

 

근데 위 식은

 

dp[1] 이 arr[0] + arr[1] 과 arr[1] 중 큰 값을 고른 값이므로

 

dp[1]+arr[2] 와 arr[2] 중 큰 값을 고르면 된다.

 

---

위와 같은 방법을 계속하면

 

dp[i] = max(dp[i-1]+arr[i], arr[i] ) 식이 나온다.