Computer >> Hướng Dẫn Máy Tính >  >> Lập Trình >> C++

Mảng tách Tổng lớn nhất trong C ++

Giả sử chúng ta có một mảng các số nguyên dương và một giá trị m. Chúng ta có thể chia mảng này thành m số mảng con liền nhau. Chúng tôi phải nghĩ ra một thuật toán để giảm thiểu tổng lớn nhất trong số m mảng con này.

Vì vậy, nếu mảng được cho là [7,2,4,10,9] và m =2, thì tổng sẽ là 19, vì chúng ta có thể tạo hai mảng con như [7,2,4] và [10,9] , thì mảng con có tổng lớn nhất là 19.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

  • Xác định một hàm splitArray (), điều này sẽ nhận một mảng v, m,
  • n:=kích thước của v
  • tạo một mảng có kích thước dp
  • tạo một tổng mảng khác có kích thước n
  • sum [0]:=v [0]
  • để khởi tạo i:=1, khi i
  • sum [i]:=sum [i - 1] + v [i]
  • dp [0]:=sum [n - 1]
  • để khởi tạo i:=1, khi i
  • dp [i]:=sum [n - 1] - sum [i - 1]
  • để khởi tạo i:=1, khi i
  • để khởi tạo start:=0, khi start
  • để khởi tạo end:=start + 1, khi end <=n - i, cập nhật (tăng end lên 1), làm -
  • dp [start]:=tối thiểu là dp [start] và tối đa là (sum [end - 1] khi start là 0, nếu không thì sum [end - 1] - sum [start - 1]) và dp [end]
  • trả về dp [0]

    • Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

    Ví dụ 

    #include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
   int splitArray(vector<int>& v, int m) {
      int n = v.size();
      vector <long long int > dp(n);
      vector <long long int> sum(n);
      sum[0] = v[0];
      for(int i =1;i<n;i++)sum[i] =sum[i-1]+v[i];
      dp[0] = sum[n-1];
      for(int i =1;i<n;i++){
         dp[i] = sum[n-1] - sum[i-1];
      }
      for(int i =1;i<m;i++){
         for(int start = 0;start<n-i;start++){
            for(int end = start+1;end<=n-i;end++){
               dp[start] = min(dp[start],max((start==0?sum[end-1]:sum[end-1]-sum[start-1]),dp[end]));
            }
         }
      }
      return dp[0];
   }
};
main(){
   Solution ob;
   vector<int> v = {7,2,4,10,9};
   cout << (ob.splitArray(v, 2));
}

    Đầu vào 

    [7,2,4,10,9]
2

    Đầu ra 

    19