Day 3 of 30-Day LeetCode Challenge

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

class Solution {
public:
int maxSubArray(vector<int>& nums) {

//kadane
int dp[nums.size()];
dp[0] = nums[0];
for(int i=1;i<nums.size();++i){
dp[i] = max(dp[i-1]+nums[i], nums[i]);
}
//now find the maximum of all dp[]’s
int result = INT_MIN;
for(int i=0;i<nums.size();++i){
result = max(result, dp[i]);
}

return result;
}
};