**** Вопрос от InterviewBit ****. Учитывая массив положительных элементов, вы должны перевернуть знак некоторых из его элементов так, чтобы результирующая сумма элементов массива была минимально неотрицательной (каккак можно ближе к нулю). Вернуть минимум нет. элементов, знак которых необходимо перевернуть так, чтобы результирующая сумма была как минимум неотрицательной.
Ограничения:
1 <= n <= 100 Сумма всех элементов не будет превышать 10 000. </p>
Пример:
A = [15, 10, 6] ans = 1 (Здесь мы перевернем знак 15 и полученная сумма будет 1)
A = [14, 10, 4] ans = 1 (Здесь мы перевернем знак 14, а полученная сумма будет 0)
Поэтому я попытался написать решение этого кода в Java.
public int solve(final List<Integer> A) {
int n=A.size();
if(n==1)
return 0;
int dp_sum[]=new int[n+1];
int dp_count[]=new int[n+1];
Collections.sort(A, Collections.reverseOrder());
int i,j,sum=0;
for(i=0;i<n;i++)
sum+=A.get(i);
for(i=0;i<=n;i++)
dp_sum[i]=sum;
//dp_sum[0]=sum;
int min_sum=sum;
int min_count=n;
for(i=1;i<=n;i++){
for(j=0;j<i;j++){
int val=dp_sum[j]-2*A.get(i-1);
if(val==0){
dp_sum[i]=val;
dp_count[i]=dp_count[j]+1;
return dp_count[i];
}
if(val>0){
if(val<dp_sum[i]){
dp_sum[i]=val;
dp_count[i]=dp_count[j]+1;
}
}
if(val<0){
if(dp_sum[j]<min_sum){
min_sum=dp_sum[j];
min_count=dp_count[j];
}
}
}
if(dp_sum[i]==sum){
dp_sum[i]=min_sum;
dp_count[i]=min_count;
}
}
return dp_count[n];
}
Итак, с тестовым примером:
[11, 10, 8, 6, 8, 11, 1, 10, 2, 3, 8, 3, 8, 12, 11,1, 7, 5, 5, 12, 9, 4, 10, 3, 3, 3, 8, 8, 8, 6, 7, 7, 7, 6, 4, 2, 5, 8, 11, 10,10, 10, 12, 9, 2, 3, 9, 12, 7, 6, 11, 8, 9, 9, 10, 3, 3, 5, 2, 10, 10, 9, 4, 9, 6,11, 10, 2, 6, 1, 4, 7, 10, 3, 4, 3, 9, 4, 3, 8, 1, 1, 3]
Ожидаемый результат: 27
Мой вывод: 28
Может кто-нибудь помочь мне с тем, где я ошибся ??