53. Maximum Subarray

[크아아아앙(rkxszkumymda)]

class Solution {

public:

int maxSubArray(vector<int>& nums) {

int dp[100001] = {0,};

dp[nums.size()-1] = nums[nums.size()-1];

int max1 = dp[nums.size()-1];

for(int i=nums.size()-2;i>=0;i--)

{

dp[i] = nums[i];

dp[i] = max(dp[i], dp[i+1] + nums[i]);

max1= max(dp[i],max1);

}

return max1;

}

};

DnC 풀이는 아직 모르겠음