Welcome to Subscribe On Youtube

2941. Maximum GCD-Sum of a Subarray

Description

You are given an array of integers nums and an integer k.

The gcd-sum of an array a is calculated as follows:

• Let s be the sum of all the elements of a.
• Let g be the greatest common divisor of all the elements of a.
• The gcd-sum of a is equal to s * g.

Return the maximum gcd-sum of a subarray of nums with at least k elements.

 

Example 1:

Input: nums = [2,1,4,4,4,2], k = 2
Output: 48
Explanation: We take the subarray [4,4,4], the gcd-sum of this array is 4 * (4 + 4 + 4) = 48.
It can be shown that we can not select any other subarray with a gcd-sum greater than 48.

Example 2:

Input: nums = [7,3,9,4], k = 1
Output: 81
Explanation: We take the subarray [9], the gcd-sum of this array is 9 * 9 = 81.
It can be shown that we can not select any other subarray with a gcd-sum greater than 81.

 

Constraints:

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

Solutions

Solution 1: Dynamic Programming

This implementation uses dynamic programming. It traverses the relevant values and updates its state as each value is processed. After all required states have been considered, the maintained result is returned.

Solution 2

This implementation uses dynamic programming. It traverses the relevant values and updates its state as each value is processed. After all required states have been considered, the maintained result is returned.

• Java
• C++
• Python
• Go
• TypeScript
• TypeScript 2

• 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;
      }
  };
  

• 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
  
  

• 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);
  }
  
  
  // Solution 2
  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);
  }
  
  

All Problems

All Solutions