我只想到了0(n^2)的：
1.先从前往后找出满足递增的情况下最后一个数最小是多少o（n^2）,（条件1）
2.再从后往前推出以每个位置开始的项能满足条件1的情况，最大能是多少o(n^2)
3.在2的结果上从前往后推每个逗号的位置，每次让当前项尽量的大o(n^2)

（当然如果您要说字符串比较也算是o(n)的话那就是o(n^3)了）- -|

付代码：

#include<cstdio>
#include<algorithm>
#include<string.h>
#include<iostream>
#include<cmath>
#include<vector>
#include<fstream>
#include<map>
#include<list>
#include<sstream>
#include<queue>
#include<set>
using namespace std;
string dp[81],s;
char f[80];
char orz(const string &x,const string &y)
{
	int lx=x.length(),ly=y.length();
	if(lx>ly) return 1;
	else if(lx<ly) return -1;
	else
	{
		if(x>y) return 1;
		else if(x<y) return -1;
		else return 0;
	}
}
int main()
{
	int l,ed2,ed1;
	while(cin>>s&&s!="0")
	{
		dp[0].clear();
		dp[0]+=char(0);
		l=s.length();
		for(int i=0;i<s.length();i++)
		{
			dp[i+1]="";
			for(int j=i;j>=0;j--)
			{
				if(dp[j]=="") continue;
				int k=j;
				while(k<=i&&s[k]=='0') k++;
				if(k>i) k--;
				string tmp=s.substr(k,i-k+1);
				if(orz(dp[j],tmp)==-1) {dp[i+1]=tmp; break;}
			}
		}
		int ll=dp[l].length();
		ed2=l-ll;
		dp[ed2]=dp[l];
		ed1=ed2;
		while(ed1-1>=0&&s[ed1-1]=='0') dp[--ed1]=dp[l];
		if(ed1==0) {cout<<s<<endl; continue;}
		for(int i=ed1-1;i>=0;i--)
		{
			dp[i]="";
			for(int j=ed2;j>i;j--)
			{
				if(dp[j]=="") continue;
				int k=i;
				while(k<=j-1&&s[k]=='0') k++;
				if(k==j) k--;
				string tmp=s.substr(k,j-k);
				if(orz(tmp,dp[j])==-1) {dp[i]=tmp; break;}
			}
		}
		memset(f,0,l);
		int start=0;
		while(start<ed1)
		{
			for(int i=ed2-1;i>=start;i--)
			{
				if(dp[i+1]=="") continue;
				int k=start;
				while(k<=i&&s[k]=='0') k++;
				if(k>i) k--;
				string tmp=s.substr(k,i-k+1);
				if(orz(tmp,dp[i+1])==-1) {f[i+1]=1; start=i+1; break;}
			}
		}
		for(int i=0;i<l;i++)
		{
			if(f[i]) cout<<',';
			cout<<s[i];
		}
		cout<<endl;
	}
}