Tổng lớn nhất của i * arr[i] trong các phép xoay mảng trong C++

Trong bài toán này, ta được cho mảng arr. Nhiệm vụ: viết chương trình tìm tổng lớn nhất của i*arr[i] trong tất cả các phép xoay của mảng cho trước trong C++.

Mô tả – tìm tổng lớn nhất trong các tổng của tất cả phần tử nhân với chỉ số của chúng {i * arr[i]} trong mỗi phép xoay.

Hãy xem ví dụ:

Input – array arr = {4, 8, 1, 5}

Output – 37

Giải thích –

Tất cả phép xoay với tổng i*arr[i] : {4, 8, 1, 5} = 4*0 + 8*1 + 1*2 + 5*3 = 25 {8, 1, 5, 4} = 8*0 + 1*1 + 5*2 + 4*3 = 23 {1, 5, 4, 8} = 1*0 + 5*1 + 4*2 + 8*3 = 37 {5, 4, 8, 1} = 5*0 + 4*1 + 8*2 + 1*3 = 23 Tổng lớn nhất là phép xoay thứ 3.

Cách đơn giản: tính tổng i*arr[i] cho mỗi phép xoay, lấy max. Xoay mảng n lần, tính tổng mỗi lần, lưu vào maxSum nếu lớn hơn.

Ví dụ

Chương trình triển khai giải pháp này:

#include<iostream> using namespace std; int findMax(int a, int b){    if(a>b)       return a; return b; } int calculateMaxSum(int arr[], int n){    int maxSum = 0, sum = 0;    for (int i=0; i<n; i++){       sum = 0;       for (int j=0; j<n; j++){          int index = (i+j)%n;          sum += j*arr[index];       }       maxSum = findMax(maxSum, sum);    }    return maxSum; } int main(){    int arr[] = {4, 8, 1, 5};    int n = sizeof(arr)/sizeof(arr[0]);    cout<<"Tổng lớn nhất của tất cả phép xoay của mảng là "<<calculateMaxSum(arr, n);    return 0; }

Kết quả

Tổng lớn nhất của tất cả phép xoay của mảng là 37

Cách hiệu quả: dùng công thức tính tổng phép xoay tiếp theo từ phép xoay trước:

nextSum = currentSum - (arraySum - arr[i-1]) + arr[i-1]*(n-1)

Dùng công thức này tìm nextSum, cuối vòng lặp so sánh nextSum với maxSum, cập nhật nếu lớn hơn.

Ví dụ

Chương trình minh họa giải pháp hiệu quả:

#include<iostream> using namespace std; int findMax(int a, int b){    if(a > b)       return a;    return b; } int calculateMaxSum(int arr[], int n){    int arraySum = 0, currentSum = 0, nextSum ;    for (int i=0; i<n; i++){       arraySum += arr[i];       currentSum += i*arr[i];    }    int maxSum = currentSum;    for (int i=1; i<n; i++){       nextSum = currentSum - (arraySum - arr[i-1]) + arr[i-1] * (n1);       currentSum = nextSum;       maxSum = findMax(maxSum, nextSum);    }    return maxSum; } int main(){    int arr[] = {4, 8, 1, 5};    int n = sizeof(arr)/sizeof(arr[0]);    cout<<"Tổng lớn nhất của tất cả phép xoay của mảng là "<<calculateMaxSum(arr, n);    return 0; }

Kết quả

Tổng lớn nhất của tất cả phép xoay của mảng là 37