leetcode

0

1 // Standard dp

2 class Solution {

3 static long long dp[2][100001];

4 long long rec(const vector<int> &nums, const int crnt, const bool odd) {

5 if (crnt >= size(nums)) return 0;

6 if (dp[odd][crnt] != -1) return dp[odd][crnt];

7 long long res =

8 max(rec(nums, crnt + 1, odd), (odd ? -1 : 1) * nums[crnt] + rec(nums, crnt + 1, !odd));

9 return dp[odd][crnt] = res;

10 }

11

12 public:

13 Solution() { memset(dp, 0xFF, sizeof(dp)); }

14 long long maxAlternatingSum(const vector<int> &nums) { return rec(nums, 0, 0); }

15 };

16

17 long long Solution::dp[2][100001];

18

19 // Optimized 1

20 class Solution {

21 public:

22 long long maxAlternatingSum(const vector<int> &nums) const {

23 long long odd = 0, even = 0;

24 for (const int n : nums) {

25 even = max(even, odd + n), odd = even - n;

26 }

27 return even;

28 }

29 };

30

31 // Optimized 2

32 class Solution {

33 public:

34 long long maxAlternatingSum(const vector<int> &nums) const {

35 long long res = nums[0];

36 for (int i = 1; i < size(nums); i++) {

37 res += max(nums[i] - nums[i - 1], 0);

38 }

39 return res;

40 }

41 };