leetcode
  • LeetCode Problems
  • Array
    • Array Partition I
    • Toeplitz Matrix
    • Find All Numbers Disappeared in an Array
    • Max Area of Island
    • Move Zeros
    • Two Sum II - Input array is sorted
    • Degree of an Array
    • Image Smoother
    • Positions of Large Groups
    • Missing Number
    • Maximum Product of Three Numbers
    • Min Cost Climbing Stairs
    • Longest Continuous Increasing Subsequence
    • Remove Element
    • Pascal's Triangle
    • Maximum Subarray
    • Largest Number At Least Twice of Others
    • Search Insert Position
    • Plus One
    • Find Pivot Index
    • Pascal's Triangle II
    • Two Sum
    • Maximize Distance to Closest Person
    • Maximum Average Subarray I
    • Remove Duplicates from Sorted Array
    • Magic Squares In Grid
    • Contains Duplicate II
    • Merge Sorted Array
    • Can Place Flowers
    • Shortest Unsorted Continuous Subarray
    • K-diff Pairs in an Array
    • Third Maximum Number
    • Rotate Array
    • Non-decreasing Array
    • Find All Duplicates in an Array
    • Teemo Attacking
    • Beautiful Arrangement II
    • Product of Array Except Self
    • Max Chunks To Make Sorted
    • Subsets
    • Best Time to Buy and Sell Stock with Transaction Fee
    • Combination Sum III
    • Find the Duplicate Number
    • Unique Paths
    • Rotate Image
    • My Calendar I
    • Spiral Matrix II
    • Combination Sum
    • Task Scheduler
    • Valid Triangle Number
    • Minimum Path Sum
    • Number of Subarrays with Bounded Maximum
    • Insert Delete GetRandom O(1)
    • Find Minimum in Rotated Sorted Array
    • Sort Colors
    • Find Peak Element
    • Subarray Sum Equals K
    • Subsets II
    • Maximum Swap
    • Remove Duplicates from Sorted Array II
    • Maximum Length of Repeated Subarray
    • Image Overlap
    • Length of Longest Fibonacci Subsequence
  • Contest
    • Binary Gap
    • Advantage Shuffle
    • Minimum Number of Refueling Stops
    • Reordered Power of 2
  • Dynamic Programming
    • Climbing Stairs
    • Range Sum Query - Immutable
    • Counting Bits
    • Arithmetic Slices
    • Palindromic Substrings
    • Minimum ASCII Delete Sum for Two Strings
    • Maximum Length of Pair Chain
    • Integer Break
    • Shopping Offers
    • Count Numbers with Unique Digits
    • 2 Keys Keyboard
    • Predict the Winner
    • Stone Game
    • Is Subsequence
    • Delete and Earn
    • Longest Palindromic Subsequence
    • Target Sum
    • Unique Binary Search Trees
    • Minimum Path Sum
    • Combination Sum IV
    • Best Time to Buy and Sell Stock with Cooldown
    • Largest Sum of Averages
    • Largest Plus Sign
    • Untitled
  • Invert Binary Tree
  • Intersection of Two Arrays
  • Surface Area of 3D Shapes
  • K Closest Points to Origin
  • Rotting Oranges
  • Smallest Integer Divisible by K
  • Duplicate Zeros
  • DI String Match
  • Implement Queue using Stacks
  • Increasing Order Search Tree
  • Reveal Cards In Increasing Order
  • Reshape the Matrix
  • Partition List
  • Total Hamming Distance
  • Validate Binary Search Tree
  • Decode Ways
  • Construct Binary Tree from Preorder and Inorder Traversal
  • Construct Binary Search Tree from Preorder Traversal
  • Design Circular Queue
  • Network Delay Time
  • Most Frequent Subtree Sum
  • Asteroid Collision
  • Binary Tree Inorder Traversal
  • Check If Word Is Valid After Substitutions
  • Construct Binary Tree from Preorder and Postorder Traversal
  • K-Concatenation Maximum Sum
Powered by GitBook
On this page
  • Description
  • Solutions
  • My solution
  • Optimal solution
  1. Dynamic Programming

Integer Break

PreviousMaximum Length of Pair ChainNextShopping Offers

Last updated 6 years ago

Description

Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get.

Example 1:

Input: 2
Output: 1
Explanation: 2 = 1 + 1, 1 × 1 = 1.

Example 2:

Input: 10
Output: 36
Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.

Note: You may assume that n is not less than 2 and not larger than 58.

Solutions

My solution

dp[i]dp[i]dp[i] : maximum product by splitting iii into at least 2 integers.

There are i−2 i - 2i−2 ways (exclusive) to split iii : split iii such that the numbers contain jjj, 0<j<i0 < j < i0<j<i.

Therefore, dp[i]=max⁡0<j<i(max⁡(j,dp[j]),i−j)dp[i] = \max_{0 < j < i}(\max(j, dp[j]), i - j)dp[i]=max0<j<i​(max(j,dp[j]),i−j)

class Solution {
public:
    int integerBreak(int n) {
        vector<int> dp(n + 1);
        dp[1] = 1;
        for(int i = 2; i <= n; ++i){
            for(int j = 1; j < i; ++j){
                dp[i] = max(dp[i], max(j, dp[j]) * (i - j));
            }
        }
        return dp[n];
    }
};

Optimal solution

Claims:

  1. The factors (integers) must be either 2 or 3.

  2. There are at most two 2s.

Proof:

  1. For any factor f larger than 3, we can further split the factor f to produce a new product that is at least as good as the old product.

  2. How to come up with claim 1?

    1. Suppose we are allowed to split n into any rational numbers.

class Solution {
public:
    int integerBreak(int n) {
        if(n == 2) return 1;
        if(n == 3) return 2;
        if(n % 3 == 0) return pow(3, n / 3);
        if(n % 3 == 1) return 4 * pow(3, (n - 4) / 3); // two 2s
        return 2 * pow(3, (n - 2) / 3); // one 2
    }
};

References:

If f is even, split f to two f/2 s. f2⋅f2≥f\frac{f}{2} \cdot \frac{f}{2} \ge f2f​⋅2f​≥f, for f≥4f \ge 4f≥4.

If f is odd, split f into (f-1)/2 and (f+1)/2. f−12⋅f+12≥f\frac{f-1}{2} \cdot \frac{f+1}{2} \ge f2f−1​⋅2f+1​≥f, for f≥5f \ge 5f≥5.

If there are more than two 2s, then we can replace three 2s to two 3s to increase the product. That is because 23<322^3 < 3^223<32.

By the , if we split n to k numbers, the product is maximized when the k numbers are equal.

So we want to find max⁡k(nk)k\max_{k} (\frac{n}{k})^kmaxk​(kn​)k. Let y=(nk)ky =(\frac{n}{k})^ky=(kn​)k. It is easy to show that yyy is maximized when k=nek = \frac{n}{e}k=en​. Therefore, the numbers are eee.

But we are only allowed to split n to integers. So we use the integers close to eee, i.e., 2 and 3.

Inequality of Square-Arithmetic and Geometric Means
A simple explanation of the math part and a O(n) solution
Why factor 2 or 3? The math behind this problem.
O(log(n)) Time solution with explanation