分離の仕方は最大で \(9! \times 8=2903040\) 通り（分離後の \(2\) 整数の順序を区別しない場合 \(\frac{2903040}{2}=1451520\) 通り）であり、小さいです。

そのためあり得る分離の仕方を全探索しても十分に実行時間制限に間に合います。

実装の際には、例えば C++ においては標準ライブラリに存在する next_permutation 関数が有用です。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
    string N; cin >> N;
    sort(N.begin(),N.end());
    int ans = 0;
    do{
        for(int i=1; i<N.size(); i++){
            string l = "", r = "";
            for(int j=0; j<i; j++) l += N[j];
            for(int j=i; j<N.size(); j++) r += N[j];
            if(l[0]=='0' || r[0]=='0') continue;
            ans = max(ans,stoi(l)*stoi(r));
        }
    }while(next_permutation(N.begin(),N.end()));
    cout << ans << endl;
}

少し考察を進めると、leading zero を許容しても答えには影響しないことが分かります。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
    string N; cin >> N;
    sort(N.begin(),N.end());
    int ans = 0;
    do{
        for(int i=1; i<N.size(); i++){
            int l = 0, r = 0;
            for(int j=0; j<i; j++) l = l*10+N[j]-'0';
            for(int j=i; j<N.size(); j++) r = r*10+N[j]-'0';
            ans = max(ans,l*r);
        }
    }while(next_permutation(N.begin(),N.end()));
    cout << ans << endl;
}

さらに考察を進めると、最大値を達成する分離の仕方において、分離後の \(2\) 変数は数字列として見たときに単調非増加であることが分かります。

これを利用すると調べ上げる必要のある分離の仕方の数は \(2^9\) 個（分離後の \(2\) 整数の順序を区別しない場合 \(2^8\) 個）であることが分かります。

実装の際は bit 全探索を用いると簡潔でしょう。

実装例 (Python)

N = sorted(input(),reverse=True)
ans = 0
for i in range(1<<len(N)):
    l = 0
    r = 0
    for j in range(len(N)):
        if i & (1<<j):
            l = l*10+ord(N[j])-ord('0')
        else:
            r = r*10+ord(N[j])-ord('0')
    ans = max(ans,l*r)
print(ans)