Why this approach is failing


#1
int Solution::solve(vector<int> &A) {
    int cost = 0;
    while(A.size()!=1){
        int index = -1;
        int mini = INT_MAX;
        int sum;
        for(int i = 0 ; i < A.size()-1 ; i++){
            sum = A[i]+A[i+1];
            if(sum<mini){index = i; mini = sum;}
        }
        //cout << index << endl;
        cost+=A[index]+A[index+1];
        A[index+1]+=A[index];
        A.erase(A.begin()+index);
    }
    return cost;
}

#2

yes , Why is it failing? If you get the reason please do share


#3

It’s failing because greedy approach is not an optimal one for this problem. Try running it on [6,4,4,6]. The correct answer is 40(10+10+20) but your algorithm will give 42(8+14+20) which is not minimal.


#4

But it’s like the merging rope question and there we use greedy i think. What’s the difference int that and in this question ?


#5

Because in Merging rope, order doesn’t matter, here only adjacent elements can be added.