CODEWITHSUNDEEP
algorithmdynamic-programmingdivide-and-conquer
Mrinal
Mrinal

Reputation: 113

Maximum sum by splitting given string

Given a string S consisting of only digits. We need to divide the string into 4 integers such that their sum is maximum. How this can be solved ? Please help

Note : Each integer should be ≤ 10^12 and should not contain any leading zeroes.

Also size of each string can be almost 20.

Example : Let S=52310 then answer is 56 as 4 integers are 52,3,1,0. So maximum sum is 56 (52 + 3 + 1 + 0).

How this can be done efficiently as I don't want to go for brute solution because of its high complexity as splitting at each available 4 positions will lead to a very ineffective approach.

Upvotes: 1

Views: 1127

Answers (1)

Heshan Sandeepa
Heshan Sandeepa

Reputation: 3687

Try this , but 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 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;     
}

Upvotes: -1

Related Questions