Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

การเพิ่มผลรวมอาร์เรย์ให้สูงสุดด้วยการดำเนินการที่กำหนดใน C++


คำอธิบาย

มีอาร์เรย์ของจำนวนเต็ม (2 * n – 1) เราสามารถเปลี่ยนเครื่องหมายขององค์ประกอบ n ตัวในอาร์เรย์ได้ กล่าวอีกนัยหนึ่ง เราสามารถเลือกองค์ประกอบอาร์เรย์ได้ n รายการ และคูณแต่ละองค์ประกอบด้วย -1 หาผลรวมสูงสุดของอาร์เรย์

ตัวอย่าง

หากอาร์เรย์อินพุตเป็น {-2, 100, -3} เราจะได้รับเครื่องหมายการเปลี่ยนแปลงสูงสุดของ -2 และ -3 หลังจากเปลี่ยนอาเรย์สัญญาณจะกลายเป็น -

{2, 100, 3} และผลรวมสูงสุดของอาร์เรย์นี้คือ 105

อัลกอริทึม

  • นับจำนวนลบ
  • คำนวณผลรวมของอาร์เรย์โดยใช้ค่าสัมบูรณ์ของตัวเลข
  • ค้นหาจำนวนขั้นต่ำของอาร์เรย์โดยใช้ค่าสัมบูรณ์ของตัวเลข
  • ตรวจสอบว่าไม่มี ของจำนวนลบเป็นเลขคี่ และค่าของ n เป็นเลขคู่ จากนั้นลบ m สองครั้งจากผลรวม และนี่จะเป็นผลรวมสูงสุดของอาร์เรย์อื่นๆ ค่าของผลรวมจะเป็นผลรวมสูงสุดของอาร์เรย์
  • ทำซ้ำขั้นตอนข้างต้น (2 * n – 1) ครั้ง

ตัวอย่าง

เรามาดูตัวอย่างกัน −

#include <bits/stdc++.h>
using namespace std;
int getMaxSum(int *arr, int n) {
   int negtiveCnt = 0;
   int sum = 0;
   int m = INT_MAX;
   for (int i = 0; i < 2 * n - 1; ++i) {
      if (arr[i] < 0) {
         ++negtiveCnt;
      }
      sum = sum + abs(arr[i]);
      m = min(m, abs(arr[i]));
   }
   if (negtiveCnt % 2 && n % 2 == 0) {
      sum = sum - 2 * m;
      return sum;
   }
   return sum;
}
int main() {
   int arr[] = {-2, 100, -3};
   int n = 2;
   cout << "Maximum sum = " << getMaxSum(arr, n) << endl;
   return 0;
}

ผลลัพธ์

Maximum sum = 105