{"id":1453,"date":"2020-06-11T04:32:21","date_gmt":"2020-06-11T04:32:21","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=1453"},"modified":"2022-03-29T10:00:10","modified_gmt":"2022-03-29T10:00:10","slug":"maximize-flip-sign","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/maximize-flip-sign\/","title":{"rendered":"MAXIMIZE FLIP SIGN"},"content":{"rendered":"

\"\"<\/p>\n

CONCEPTS USED:<\/h3>\n
\n

Greedy algorithm.<\/p>\n<\/blockquote>\n

DIFFICULTY LEVEL:<\/h3>\n
\n

Medium.<\/p>\n<\/blockquote>\n

PROBLEM STATEMENT(<\/code>SIMPLIFIED)<\/code>:<\/h3>\n
\n

Tina knows PrepBuddy likes to play games with array elements. So she gave PrepBuddy an array A containing N integers. She wants to know the maximum possible sum of the array after performing the following operation M number of times:<\/p>\n

    \n
  1. Choose an index i and flip the sign of the element present at that index, i.e replace A[i] with \u2212A[i].<\/li>\n
  2. It is allowed to choose the same index multiple times.<\/li>\n<\/ol>\n<\/blockquote>\n

    <\/strong><\/u><\/a><\/p>\n

    For Example :<\/h4>\n
    2\n5 4\n-3 7 -1 -5 -3\n4 3\n-4 2 3 1\n\n19\n10\n\nIn the first test case choose index [0,2,3,4], so the array becomes [3,7,1,5,3] and the sum = 19.\n\nIn the second test case choose index [0,3,3], so the array becomes [4,2,3,1] and the sum = 10.<\/code><\/pre>\n
    OBSERVATION:<\/h3>\n
    \n
    We need to flip the smallest number in each iteration!!<\/p>\n<\/blockquote>\n
    SOLVING APPROACH:<\/h3>\n
    \n
    We need to flip the smallest number in each iteration.Why??<\/p>\n
    If the smallest number is negative ,flipping it would give us a positive number hence increasing our maximum sum.<\/p>\n
    If the smallest number is positive ,flipping it will reduce the sum but flipping any other number greater than it would lessen the sum even more.<\/p>\n
    Follow the algorithm:<\/p>\n
    Push all the given element in priority queue.<\/p>\n
    Now iterate till m and pop the top element of the queue ,flip it and push it back.<\/p>\n
    Remember to update the sum at each step.<\/p>\n
    Can you notice that we used greedy approach here??Remember what greedy says?<\/em><\/p>\n<\/blockquote>\n
    Always make the choice that seems to be the best at that moment. This means that make a locally-optimal choice in the hope that this choice will lead to a globally-optimal solution. That is what we did!<\/p>\n
    SOLUTIONS:<\/h3>\n\t\t\t\t\t\t