Leetcode 343 Solution

This article provides solution to leetcode question 343 (integer-break)

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