Maximum Subarray

HouseRobber이랑 꽤 비슷한 패턴을 느껴서 천천히 풀어봤고 바로 맞출 수 있었다. 결국 이 문제는 겹치는 구간에서 가장 최대값만 남기면서 가면 되는 문제이다. 그러기 위해서는 바로 전까지 이어지는 가장 큰 값과 현재를 더할것이냐 아니면 전 값을 버리고 내 현재 값부터 시작할것이냐로 갈려진다.

그것만 잘 유의하고 문제를 푼다면 문제 없이 잘 풀 수 있다.

자바의 스트림 관련해서 참고한 링크다:
스트림1
스트림2

class Solution {
    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length]; 
        dp[0] = nums[0]; 
        for(int i = 1; i < nums.length; i++){
            dp[i] = Math.max(nums[i],dp[i-1] + nums[i]); 
        }
        
        return Collections.max(Arrays.stream(dp).boxed().toList()); 
    }
}
//더했을때 Max값 
//그냥 혼자서의 Max 값 

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        vector<int> dp(nums.size(),0); 
        dp[0] = nums[0]; 
        for(int i = 1; i < nums.size(); i++){
            dp[i] = max(dp[i-1] + nums[i], nums[i]); 
        }
        return *max_element(dp.begin(),dp.end()); 
    }
};