Максимальная сумма путем разбиения заданной строки

Question

Учитывая строку S, состоящую только из цифр. Нам нужно разделить строку на 4 целых числа, чтобы их сумма была максимальной. Как это можно решить? Пожалуйста, помогите

Примечание: каждое целое число должно быть ≤ 10^12 и не должно содержать никаких ведущих нулей.

Кроме того, размер каждой строки может быть почти 20.

Пример: Пусть S = 52310, то ответ 56 как 4 целые числа 52,3,1,0. Таким образом, максимальная сумма равна 56 (52 + 3 + 1 + 0).

Как это можно сделать эффективно, так как я не хочу идти на грубое решение из-за его высокой сложности, так как расщепление на каждом доступном 4-х позициях приведет к очень неэффективному подходу.

Answer 1

Попробуйте это, но в 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 i = 0; i < arr.length ; i ++) 
    { 
     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;  
}