algorithm - Maximum sum by splitting given string -

given string s consisting of digits. need divide string 4 integers such sum maximum. how can solved ? please help

note : each integer should ≤ 10^12 , should not contain leading zeroes.

also size of each string can 20.

example : let s=52310 answer 56 4 integers 52,3,1,0. maximum sum 56 (52 + 3 + 1 + 0).

how can done efficiently don't want go brute solution because of high complexity splitting @ each available 4 positions lead ineffective approach.

try , in java

    private void method() {     string value = "52310";     string sortedstring ;     int stringlength;     long total = 0;       char[] arr = value.tochararray();     list<string> seperatedintegers = new arraylist<string>();      if(arr.length > 3)     {         sortedstring = sort(arr);         stringlength = sortedstring.length();          for(int m = 0 ; m < 3 ; m ++)         {             seperatedintegers.add(sortedstring.substring(stringlength - 1, stringlength));                       stringlength--;         }          seperatedintegers.add(sortedstring.substring(0, stringlength));                      }        if(seperatedintegers.size() > 0)     {         for(int n = 0 ; n < seperatedintegers.size() ; n ++)         {             total = total + long.valueof(seperatedintegers.get(n));          }        }      toast.maketext(getapplicationcontext(), string.valueof(total), toast.length_long).show();  }  private string sort(char[] arr) {     int temp;     string val = "";      list<integer> sortedvalues  = new arraylist<integer>();      for(int = 0; < arr.length ; ++)     {         sortedvalues.add(integer.valueof(string.valueof(arr[i])));     }       for(int j = 1; j < sortedvalues.size();  j++)     {         for(int k = j; k > 0; k--)         {             if(sortedvalues.get(k) > sortedvalues.get(k-1))             {                 temp=sortedvalues.get(k);                 sortedvalues.set(k, sortedvalues.get(k-1));                 sortedvalues.set(k - 1, temp);             }         }     }      for(int l = 0; l < sortedvalues.size() ; l ++)     {         val = val + string.valueof(sortedvalues.get(l));     }      return val;      }