力扣每日一题（2023年7月）

1、7月11日 1911. 最大子序列交替和

思路：动态规划

（动态规划分析步骤：确定dp数组下标及含义，确定dp数组的递推公式，dp数组初始化，确定遍历顺序）

和122. 买卖股票的最佳时机 II类似，设dp[i][0]为从nums[0]，nums[1]，…，nums[i]中选择一个子序列，并且该子序列最后一个元素的下标为偶数的最大交替和；设dp[i][1]为从nums[0]，nums[1]，…，nums[i]中选择一个子序列，并且该子序列最后一个元素的下标为奇数的最大交替和。

• 对于dp[i][0]可以由两个状态推导：
  • 不选择nums[i]，则dp[i][0]=dp[i-1][0]
  • 选择nums[i]，则dp[i][0]=dp[i-1][1]+nums[i]
• 对于dp[i][1]可以由两个状态推导：
  • 不选择nums[i]，则dp[i][1]=dp[i-1][1]
  • 选择nums[i]，则dp[i][1]=dp[i-1][0]-nums[i]

初始化：dp[i][0]=nums[0]，dp[i][1]=0；遍历顺序：因为dp[i]由dp[i-1]确定，所以由前到后遍历

最大的交替和的子序列最后一个元素一定是偶数，所以最终返回dp[nums.size() - 1][0]

C++代码

class Solution {
public:
    long long maxAlternatingSum(vector<int>& nums) {
        vector<vector<long long>> dp(nums.size(), vector<long long>(2, 0));
        dp[0][0] = nums[0];
        dp[0][1] = 0;
        for (int i = 1; i < nums.size(); i++) {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + nums[i]);
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - nums[i]);
        }
        return dp[nums.size() - 1][0];
    }
};

2、7月12日 2544. 交替数字和

思路

由题意可知n的最高位符号为正，后面位按负正负正…的顺序，而我们通常通过倒序获得一个整数的各个位的值，因此如果知道最后一位的符号即可按倒序求解交替数字的和。如果n由奇数位组成则最后一位符号为正，由偶数位组成则最后一位符号为负，因此首先求n有多少位（可以先将n转为string，进而获取位数的奇偶性）。

C++代码

class Solution {
public:
    int alternateDigitSum(int n) {
        int res = 0;
        int flag = to_string(n).size() % 2 == 1 ? 1 : -1;
        while (n > 0) {
            int num = n % 10;
            n /= 10;
            res += flag * num;
            flag = -flag;
        }
        return res;
    }
};