leetcode

0 // memorization approach

1 class Solution {

2 public:

3 int maxSubArray(vector<int> &nums) {

4 int n = nums.size(), maxi;

5 vector<int> dp(n);

6

7 maxi = dp[0] = nums[0];

8 for (int i = 1; i < n; i++) {

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

10 maxi = max(maxi, dp[i]);

11 }

12 return maxi;

13 }

14 };

15

16 // optimized, memorize only the previous value

17 class Solution {

18 public:

19 int maxSubArray(vector<int> &nums) {

20 int n = nums.size(), maxi, prev;

21 maxi = prev = nums[0];

22 for (int i = 1; i < n; i++)

23 maxi = max(maxi, prev = nums[i] + max(prev, 0));

24 return maxi;

25 }

26 };