给定一个正整数 NN 。你可以对 NN 的任意一位数字执行任意次以下 2 种操 作： 将该位数字加 1 。如果该位数字已经是 9 , 加 1 之后变成 0 。 将该位数字减 1 。如果该位数字已经

是 0 , 减 1 之后变成 9 。

你需要通过执行上述操作，使得 NN 的各位数字之和最大化。请你输出最大的数字和。

输入格式
输入一个正整数 NN 。

输出格式
输出一个正整数，表示 NN 的各位数字之和最大值。

数据范围
1≤N≤10181≤N≤1018

输入样例1：
10
输出样例1：
10
输入样例2：
128
输出样例2：
20
输入样例3：
358
输出样例3：
27
输入样例4：
987654321
输出样例4：
81

分析

1.将数字N分解成各个位上的数字，存到数组c中

2.从高位到低位遍历数组c，对于每个c[i]进行以下操作：

如果c[i]<=4, 则将c[i]加到sum中
如果c[i]>4, 且i!=0, 则将sum+10^(i-1)加到sum中
如果c[i]>4, 且i==0, 则将sum+1加到sum中

3.输出sum

时间复杂度 O(lgn)