# 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;

}

};