Leetcode 343 Solution

This article provides solution to leetcode question 343 (integer-break)
Categories:
Tags:
Access this page by simply typing in "lcs 343" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/integer-break

Solution

class Solution {
public:
    int integerBreak(int n) {
        if (n <= 1)
            return 0;
        else if (n == 2)
            return 1;
        else if (n == 3)
            return 2;

        vector<int> a(n + 1);
        a[0] = a[1] = 1;
        a[2] = 2;
        a[3] = 3;

        for (int i = 4; i <= n; i++)
        {
            for (int j = 2; j <= i - 2; j++)
                a[i] = max(a[i], a[i - j] * j);
        }

        return a[n];
    }
};