Question

2941. 子数组的最大 GCD-Sum

English Version

题目描述

给定一个整数数组 nums 和一个整数 k.

数组 a 的 gcd-sum 计算方法如下：

• 设 s 为 a 的所有元素的和。
• 设 g 为 a 的所有元素的 最大公约数。
• a 的 gcd-sum 等于 s * g.

返回 _nums 的至少包含 k 个元素的子数组的 最大 gcd-sum。_

 

示例 1：

输入：nums = [2,1,4,4,4,2], k = 2
输出：48
解释：我们选择子数组 [4,4,4]，该数组的 gcd-sum 为 4 * (4 + 4 + 4) = 48。
可以证明我们无法选择任何其他 gcd-sum 大于 48 的子数组。

示例 2：

输入：nums = [7,3,9,4], k = 1
输出：81
解释：我们选择子数组 [9]，该数组的 gcd-sum 为 9 * 9 = 81。
可以证明我们无法选择任何其他 gcd-sum 大于 81 的子数组。

 

提示：

• n == nums.length
• 1 <= n <= 105
• 1 <= nums[i] <= 106
• 1 <= k <= n

解法

方法一

class Solution:
  def maxGcdSum(self, nums: List[int], k: int) -> int:
    s = list(accumulate(nums, initial=0))
    f = []
    ans = 0
    for i, v in enumerate(nums):
      g = []
      for j, x in f:
        y = gcd(x, v)
        if not g or g[-1][1] != y:
          g.append((j, y))
      f = g
      f.append((i, v))
      for j, x in f:
        if i - j + 1 >= k:
          ans = max(ans, (s[i + 1] - s[j]) * x)
    return ans

class Solution {
  public long maxGcdSum(int[] nums, int k) {
    int n = nums.length;
    long[] s = new long[n + 1];
    for (int i = 1; i <= n; ++i) {
      s[i] = s[i - 1] + nums[i - 1];
    }
    List<int[]> f = new ArrayList<>();
    long ans = 0;
    for (int i = 0; i < n; ++i) {
      List<int[]> g = new ArrayList<>();
      for (var e : f) {
        int j = e[0], x = e[1];
        int y = gcd(x, nums[i]);
        if (g.isEmpty() || g.get(g.size() - 1)[1] != y) {
          g.add(new int[] {j, y});
        }
      }
      f = g;
      f.add(new int[] {i, nums[i]});
      for (var e : f) {
        int j = e[0], x = e[1];
        if (i - j + 1 >= k) {
          ans = Math.max(ans, (s[i + 1] - s[j]) * x);
        }
      }
    }
    return ans;
  }

  private int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
  }
}

class Solution {
public:
  long long maxGcdSum(vector<int>& nums, int k) {
    int n = nums.size();
    long long s[n + 1];
    s[0] = 0;
    for (int i = 1; i <= n; ++i) {
      s[i] = s[i - 1] + nums[i - 1];
    }
    vector<pair<int, int>> f;
    long long ans = 0;
    for (int i = 0; i < n; ++i) {
      vector<pair<int, int>> g;
      for (auto [j, x] : f) {
        int y = gcd(x, nums[i]);
        if (g.empt() || g.back().second != y) {
          g.emplace_back(j, y);
        }
      }
      f = move(g);
      f.emplace_back(i, nums[i]);
      for (auto [j, x] : f) {
        if (i - j + 1 >= k) {
          ans = max(ans, (s[i + 1] - s[j]) * x);
        }
      }
    }
    return ans;
  }
};

func maxGcdSum(nums []int, k int) int64 {
  n := len(nums)
  s := make([]int64, n+1)
  s[0] = 0
  for i, x := range nums {
    s[i+1] = s[i] + int64(x)
  }
  type pair [2]int
  var f []pair
  var ans int64
  for i := 0; i < n; i++ {
    var g []pair
    for _, p := range f {
      j, x := p[0], p[1]
      y := int(gcd(int(x), nums[i]))
      if len(g) == 0 || g[len(g)-1][1] != y {
        g = append(g, pair{j, y})
      }
    }
    f = g
    f = append(f, pair{i, nums[i]})
    for _, p := range f {
      j, x := p[0], p[1]
      if i-j+1 >= k {
        ans = max(ans, (s[i+1]-s[j])*int64(x))
      }
    }
  }
  return ans
}

func gcd(a, b int) int {
  if b == 0 {
    return a
  }
  return gcd(b, a%b)
}

function maxGcdSum(nums: number[], k: number): number {
  const n: number = nums.length;
  const s: number[] = Array(n + 1).fill(0);
  for (let i = 1; i <= n; i++) {
    s[i] = s[i - 1] + nums[i - 1];
  }

  let f: [number, number][] = [];
  let ans: number = 0;

  for (let i = 0; i < n; ++i) {
    const g: [number, number][] = [];
    for (const [j, x] of f) {
      const y: number = gcd(x, nums[i]);
      if (g.length === 0 || g.at(-1)[1] !== y) {
        g.push([j, y]);
      }
    }
    f = g;
    f.push([i, nums[i]]);
    for (const [j, x] of f) {
      if (i - j + 1 >= k) {
        ans = Math.max(ans, (s[i + 1] - s[j]) * x);
      }
    }
  }

  return ans;
}

function gcd(a: number, b: number): number {
  return b === 0 ? a : gcd(b, a % b);
}

方法二

function maxGcdSum(nums: number[], k: number): number {
  const n: number = nums.length;
  const s: number[] = Array(n + 1).fill(0);
  for (let i = 1; i <= n; i++) {
    s[i] = s[i - 1] + nums[i - 1];
  }

  let f: [number, number][] = [];
  let ans: number = 0;

  for (let i = 0; i < n; ++i) {
    const g: [number, number][] = [];
    for (const [j, x] of f) {
      const y: number = gcd(x, nums[i]);
      if (g.length === 0 || g.at(-1)[1] !== y) {
        g.push([j, y]);
      }
    }
    f = g;
    f.push([i, nums[i]]);
    for (const [j, x] of f) {
      if (i - j + 1 >= k) {
        ans = Math.max(ans, (s[i + 1] - s[j]) * x);
      }
    }
  }

  return ans;
}

function gcd(a: number, b: number): number {
  return b === 0 ? a : gcd(b, a % b);
}