This is the 26th day of my participation in the August Text Challenge.More challenges in August

Note: Part of the article content and pictures from the network, if there is infringement please contact me (homepage public number: small siege lion learning front)

By: Little front-end siege lion, home page: little front-end siege lion home page, source: Nuggets

GitHub: P-J27, CSDN: PJ wants to be a front-end siege lion

Copyright belongs to the author. Commercial reprint please contact the author for authorization, non-commercial reprint please indicate the source.

LeetCode 343. Integer split – JavaScript

Topic describes

Given a positive integer n, split it into the sum of at least two positive integers and maximize the product of these integers. Returns the largest product you can get.

Subject analysis

N can be split into at least the sum of two positive integers.

For 7, we can split it into 3+4, and the largest product is 12.

For 8, we can split it into 3+3+2, and the largest product is 18.

Solution 1: Dynamic programming

The state array dp[I] represents: the number I is split into the largest product of the sum of at least two positive integers. For ease of calculation, dp has length n + 1 and the value is initialized to 1.

Obviously dp[2] is equal to 1, and the outer loop starts at 3 and stops at n. The inner loop j starts at 1 and stops at I, which means the number I can be split into j + (i-j). But j * (i-j) is not necessarily the largest product, because i-j is not necessarily greater than dp[i-j] (the largest product of numbers i-j divided into the sum of integers), and the largest value is chosen here as the result of dp[I].

The space complexity is O(N)O(N)O(N) O(N), and the time complexity is O(N2)O(N^2)O(N2). The code implementation is as follows:

/ * * *@param {number} n
 * @return {number}* /
var integerBreak = function(n) {
  const dp = new Array(n + 1).fill(1);
​
  for (let i = 3; i <= n; ++i) {
    for (let j = 1; j < i; ++j) {
      dp[i] = Math.max(dp[i], j * (i - j), j * dp[i - j]); }}return dp[n];
};
Copy the code

Solution 2: The greedy method

Try a few more examples and find a pattern. So here’s my way of looking for patterns.

As mentioned earlier: 8 is split into 3+3+2, where the product is maximum. And then you figure out an integer, and you break it up into multiple sums of 2’s and 3’s to maximize the product. The principle is easy to understand because 2 and 3 can be combined into any number. For example, 5=2+3, but 5 < 2*3; For example, 6=3+3, but 6<3*3. So, according to the greedy algorithm, we try to split the original number into as many 3’s as possible, and then into as many 2’s as possible, so that the product of the integers we split is the largest.

But the above solution is not enough. If the integer n is of the form 3k+1, for example, 7. According to the above rules, it will be divided into “3 + 3 + 1”. But in the multiplication operation, 1 doesn’t matter. At this point, 1 and 3 should be turned into 4, so “3 + 3 + 1” becomes “3 + 4”. The product is at its maximum.

To sum up, the overall idea of the algorithm is as follows:

  • N divided by 3 is a, remainder b
  • When b is 0, you just multiply a times 3
  • When b is 1, you multiply a minus 1 3 times 4
  • When b is 2, multiply a 3’s by 2

The space complexity is O(1), the time complexity is O(1). The code implementation is as follows:

/ * * *@param {number} n
 * @return {number}* /
var integerBreak = function(n) {
  if (n === 2) return 1;
  if (n === 3) return 2;
  // The number of 3's that n can split into
  const a = Math.floor(n / 3);
  const b = n % 3;
​
  // n is a multiple of 3
  if (b === 0) return Math.pow(3, a);
  // n is 3k + 1, for example, 7. Let's break it into 3, 3, 1. Since one can't contribute to the result, the final three and one are replaced with four
  if (b === 1) return Math.pow(3, a - 1) * 4;
  return Math.pow(3, a) * 2;
};
Copy the code

Thank you for reading, I hope to help you, if there is a mistake or infringement of the article, you can leave a message in the comment area or add a public number in my home page to contact me.

Writing is not easy, if you feel good, you can “like” + “comment” thanks for your support ❤