给定 n，找到相加得到 n 的最大数

oracle面试时问的问题。例如，如果我的输入是6，那么

• 5+1=6 且：2
• 4+2=6 且：2
• 3+2+1=6 且：3

所以，最终答案应该是3。（即需要3,2,1才能得到总和6）

Note：不允许数字重复（即1+1+1+1+1+1=6）

我用递归解决了这个问题，但面试官不满意。动态规划可能吗？

x 个数的最小和为

所以只要找到满足不等式的x：

这是代码：

#include <stdio.h>

int main() {
    int n;
    scanf("%d", &n);
    int x = 1;
    while ((x+1)*x/2 <= n) x++;
    x--; // now (x+1)*x/2 > n , so x is too large
    printf("%d\n", x);
    return 0;
}

如果 n 很大，可以使用二分查找。