JAVA O(n) solution
class Solution {\n    public int maxProductDifference(int[] nums) {\n    \n        int l1=0,l1_index=0,l2=0;\n        \n        //Find max1\n        for(int i=0
class Solution {\n    public int maxProductDifference(int[] nums) {\n    \n        int l1=0,l1_index=0,l2=0;\n        \n        //Find max1\n        for(int i=0;i<nums.length;i++)\n        {\n            if(nums[i]>l1){\n                l1=nums[i];\n                l1_index=i;\n            }\n        }\n        \n        //Find max2\n        for(int i=0;i<nums.length;i++){\n            if(i!=l1_index && nums[i]>l2)\n                l2=nums[i];\n        }\n      \n        if(l2==0)\n            l2=l1;\n        \n          //Find min1\n          int s1=l1,s1_index=0,s2=l1;\n          for(int i=0;i<nums.length;i++)\n          {\n              if(nums[i]<s1)\n              {\n                  s1=nums[i];\n                  s1_index=i;\n              }\n          }\n        \n        //Find min2\n         for(int i=0;i<nums.length;i++){\n            if(i!=s1_index && nums[i]<s2)\n                s2=nums[i];\n        }\n\n        //Product\n        int prd=(l1*l2)-(s1*s2);\n\n        return prd;\n    }\n}
[]