游游的最大gcd - 携程笔试

题目描述

游游拿到了一个长度为n的数组 ，请你在不改变元素原有顺序的情况下将其分成恰好m个非空子数组，对m个子数组分别计算数组内所有元素的gcd值，请问这m个非空子数组内部的gcd值之和的最大值是多少。

最大公约数(gcd)指能够整除多个非零整数的最大正整数。分割指的是将数组分成若干个连续的子数组，每个元素都必须分到一个子数组中，且子数组之间不能有重叠部分，子数组的并集要能够完全覆盖整个数组。

输入

第一行两个整数表示n,m。 第二行几个整数表示数组 a[i]。

输出

输出一行一个整数表示答案。

示例1

输入：
4 2
5 6 3 2

输出：
6

题解

这个问题可以用动态规划来解决。我们可以使用一个二维数组 dp 来表示前 i 个元素被分成 j 段的情况下，GCD 和的最大值。为了更高效地计算子数组的 GCD，我们可以提前预处理每个子数组的 GCD 值。

代码思路：

1. 预处理 GCD 值：
   • 使用 gcd[i][j] 表示从第 i 个元素到第 j 个元素的 GCD 值，使用递推的方式计算所有子数组的 GCD。
2. 动态规划数组 dp:
   • dp[i][j] 表示前 i 个元素被分成 j 段时，所有段的 GCD 和的最大值。
   • 初始化 dp[0][0] = 0，即前 0 个元素分成 0 段时的 GCD 和为 0。
3. 状态转移方程:
   • 对于每个位置 i 和每个分段数 j，我们尝试将 i 前面的部分分为 j-1 段，然后把 i 开始的部分作为新的子段： 其中 k 是上一个子段的结束位置。
4. 输出结果：
   • 最终 dp[n][m] 就是我们要找的答案。

C++

#include <iostream>
#include <vector>
#include <algorithm>

us