Solution 2 for Scaler Topics Fortnightly Contest - 14

This article is part of the Scaler Topics Fortnightly Contest - 14

Transform Your Career

Choose from our industry-leading programs designed for career success

NSDC Certified

Modern Software and AI Engineering Program

Master full-stack development with AI integration

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

Modern Data Science and ML with specialisation in AI

Advanced data science techniques with AI specialization

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

Advanced AIML with Specialisation in Agentic AI

Deep dive into AIML with focus on Agentic systems

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

DevOps, Cloud & AI Platform Engineering

Build and manage AI-powered cloud infrastructure

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

AI Engineering Advanced Certification by IIT-Roorkee

Premier AI engineering certification from IIT-Roorkee

3 MonthsDuration

AI-LedCurriculum

Career SupportSupport

Go to Program

Solution Approach

• The positive elements should be in the same subset to maximize the power. Instead of multiple negative elements in a single subset, they should be in different subsets.
• We can include some negative elements with the subset with positive ones. Including a greater negative part is more beneficial than including a smaller negative element.
• Sort the harmful elements in decreasing order. Brute force over them and pick the best possible power.
• Pseudocode: $l = len(pos)$ $x = sum(pos)$ $y = sum(neg)$ $ans = l * x + y$ $neg.sort(reverse=True)$ for i in neg: $l += 1$ $x += i$ $y -= i$ $ans = max(ans, l * x + y)$

Time Complexity- $O(N * log(N))$

Space Complexity- $O(N)$

C++ Implementation

Java Implementation

Hiring Partners:

GoogleAmazonMicrosoftFlipkartAdobe1200+ more

Python Implementation