Select two equally-sized disjoint subarrays, A and B, that maximise the sum (A_1*B_k + A_2*B_(k-1) … + A_k*B_1), k = |A| = |B|

huangapple
go评论106阅读模式
英文:

Select two equally-sized disjoint subarrays, A and B, that maximise the sum (A_1*B_k + A_2*B_(k-1) ... + A_k*B_1), k = |A| = |B|

问题

  1. import java.util.Scanner;
  2. import java.util.*;
  4. public class Main {
  5. 	
  6. 	static class pair {
  7. 		int first, second;
  8. 		
  9. 		public pair(int first, int second) {
  10. 			this.first = first;
  11. 			this.second = second;
  12. 		}
  13. 	}
  14. 	
  15. 	static int getSubarraySum(int sum[], int i, int j) {
  16. 		if (i == 0)
  17. 			return sum[j];
  18. 		else
  19. 			return (sum[j] - sum[i - 1]);
  20. 	}
  21. 	
  22. 	static int maximumSumTwoNonOverlappingSubarray(int arr[], int N, int K) {
  23. 		int l = 0, m = 0;
  24. 		int a1[] = new int[N / 2];
  25. 		int a2[] = new int[N / 2];
  26. 		int prod = 0;
  27. 		int[] sum = new int[N];
  28. 		sum[0] = arr[0];
  29. 		
  30. 		for (int i = 1; i < N; i++)
  31. 			sum[i] = sum[i - 1] + arr[i];
  32. 		
  33. 		pair resIndex = new pair(N - 2 * K, N - K);
  34. 		
  35. 		int maxSum2Subarray =
  36. 				getSubarraySum(sum, N - 2 * K, N - K - 1)
  37. 						+ getSubarraySum(sum, N - K, N - 1);
  38. 		
  39. 		pair secondSubarrayMax =
  40. 				new pair(N - K, getSubarraySum(sum, N - K, N - 1));
  41. 		
  42. 		for (int i = N - 2 * K - 1; i >= 0; i--) {
  43. 			int cur = getSubarraySum(sum, i + K, i + 2 * K - 1);
  44. 			if (cur >= secondSubarrayMax.second)
  45. 				secondSubarrayMax = new pair(i + K, cur);
  46. 			cur = getSubarraySum(sum, i, i + K - 1)
  47. 					+ secondSubarrayMax.second;
  48. 			if (cur >= maxSum2Subarray) {
  49. 				maxSum2Subarray = cur;
  50. 				resIndex = new pair(i, secondSubarrayMax.first);
  51. 			}
  52. 		}
  53. 		
  54. 		for (int i = resIndex.first; i < resIndex.first + K; i++) {
  55. 			a1[l] = arr[i];
  56. 			l++;
  57. 		}
  58. 		
  59. 		for (int i = resIndex.second; i < resIndex.second + K; i++) {
  60. 			a2[m] = arr[i];
  61. 			m++;
  62. 		}
  63. 		
  64. 		for (int i = 0; i < m; i++) {
  65. 			if (a1[i] != 0 || a2[i] != 0) {
  66. 				prod = prod + a1[i] * a2[m - (i + 1)];
  67. 			}
  68. 		}
  69. 		return prod;
  70. 	}
  71. 	
  72. 	public static void main(String[] args) {
  73. 		Scanner sc = new Scanner(System.in);
  74. 		int a = sc.nextInt();
  75. 		int k = 0;
  76. 		int arr[] = new int[a];
  77. 		
  78. 		for (int i = 0; i < a; i++) {
  79. 			arr[i] = sc.nextInt();
  80. 		}
  81. 		
  82. 		int l = arr.length;
  83. 		int ar[] = new int[a / 2];
  84. 		
  85. 		for (int i = 1; i <= a / 2; i++) {
  86. 			ar[k] = maximumSumTwoNonOverlappingSubarray(arr, l, i);
  87. 			k++;
  88. 		}
  89. 		
  90. 		Arrays.sort(ar);
  91. 		System.out.println(ar[k - 1]);
  92. 	}
  93. }

Please note that I've only provided the translated code without any changes to the logic or structure. If you need assistance with understanding or debugging the code, feel free to ask.

英文:

A food fest is organised at the JLN stadium. The stalls from different states and cities have been set up. To make the fest more interesting, multiple games have been arranged which can be played by the people to win the food vouchers.One such game to win the food vouchers is described below:

There are N number of boxes arranged in a single queue. Each box has an integer I written on it. From the given queue, the participant has to select two contiguous subsequences A and B of the same size. The selected subsequences should be such that the summation of the product of the boxes should be maximum. The product is not calculated normally though. To make the game interesting, the first box of subsequence A is to be multiplied by the last box of subsequence B. The second box of subsequence A is to be multiplied by the second last box of subsequence B and so on. All the products thus obtained are then added together.

If the participant is able to find the correct such maximum summation, he/she will win the game and will be awarded the food voucher of the same value.

Note: The subsequences A and B should be disjoint.

Example:

Number of boxes, N = 8

The order of the boxes is provided below:

1 9 2 3 0 6 7 8

Subsequence A

9 2 3

Subsequence B

6 7 8

The product of the subsequences will be calculated as below:

P1 = 9 * 8 = 72

P2 = 2 * 7 = 14

P3 = 3 * 6 = 18

Summation, S = P1 + P2 + P3 = 72 + 14 + 18 = 104

This is the maximum summation possible as per the requirement for the given N boxes.

Tamanna is also in the fest and wants to play this game. She needs help in winning the game and is asking for your help. Can you help her in winning the food vouchers?

Input Format

The first line of input consists of the number of boxes, N.

The second line of input consists of N space-separated integers.

Constraints

1< N <=3000

-10^6 <= I <=10^6

Output Format
Print the maximum summation of the product of the boxes in a separate line.

Sample TestCase 1
input

  1. 8
  2. 1 9 2 3 0 6 7 8

output

  1. 104

my code is this it is passing only one test can anyone tell me what is wrong and i don't have other test cases since they r hidden

  1. import java.util.Scanner;
  2. import java.util.*;
  3. public class Main {
  4. static class pair {
  5. int first, second;
  6. public pair(int first, int second) {
  7. this.first = first;
  8. this.second = second;
  9. }
  10. }
  11. static int getSubarraySum(int sum[], int i, int j) {
  12. if (i == 0)
  13. return sum[j];
  14. else
  15. return (sum[j] - sum[i - 1]);
  16. }
  17. static int maximumSumTwoNonOverlappingSubarray(int arr[], int N,
  18. int K) {
  19. int l = 0, m = 0;
  20. int a1[] = new int[N / 2];
  21. int a2[] = new int[N / 2];
  22. int prod = 0;
  23. int[] sum = new int[N];
  24. sum[0] = arr[0];
  25. for (int i = 1; i &lt; N; i++)
  26. sum[i] = sum[i - 1] + arr[i];
  27. pair resIndex = new pair(N - 2 * K, N - K);
  28. int maxSum2Subarray =
  29. getSubarraySum(sum, N - 2 * K, N - K - 1)
  30. + getSubarraySum(sum, N - K, N - 1);
  31. pair secondSubarrayMax =
  32. new pair(N - K, getSubarraySum(sum, N - K, N - 1));
  33. for (int i = N - 2 * K - 1; i &gt;= 0; i--) {
  34. int cur = getSubarraySum(sum, i + K, i + 2 * K - 1);
  35. if (cur &gt;= secondSubarrayMax.second)
  36. secondSubarrayMax = new pair(i + K, cur);
  37. cur = getSubarraySum(sum, i, i + K - 1)
  38. + secondSubarrayMax.second;
  39. if (cur &gt;= maxSum2Subarray) {
  40. maxSum2Subarray = cur;
  41. resIndex = new pair(i, secondSubarrayMax.first);
  42. }
  43. }
  44. for (int i = resIndex.first; i &lt; resIndex.first + K; i++) {
  45. a1[l] = arr[i];
  46. l++;
  47. }
  48. for (int i = resIndex.second; i &lt; resIndex.second + K; i++) {
  49. a2[m] = arr[i];
  50. m++;
  51. }
  52. for (int i = 0; i &lt; m; i++) {
  53. if (a1[i] != 0 || a2[i] != 0) {
  54. prod = prod + a1[i] * a2[m - (i + 1)];
  55. }
  56. }
  57. return prod;
  58. }
  59. public static void main(String[] args) {
  60. Scanner sc = new Scanner(System.in);
  61. int a = sc.nextInt();
  62. int k = 0;
  63. int arr[] = new int[a];
  64. for (int i = 0; i &lt; a; i++) {
  65. arr[i] = sc.nextInt();
  66. }
  67. int l = arr.length;
  68. int ar[] = new int[a / 2];
  69. for (int i = 1; i &lt;= a / 2; i++) {
  70. ar[k] = maximumSumTwoNonOverlappingSubarray(arr, l, i);
  71. k++;
  72. }
  73. Arrays.sort(ar);
  74. System.out.println(ar[k - 1]);
  75. }
  76. }

答案1

得分: 3

这是一个时间复杂度为O(n^2)，空间复杂度为O(1)的解决方案。

让我们在矩阵中列出所有O(n^2)的倍数。例如：

  1. 输入 {1, 2, 3, -4, 5, 6}
  2. 1   2   3  -4   5   6
  3. 1  x   2   3  -4   5   6
  4. 2      x   6  -8  10  12
  5. 3          x -12  15  18
  6. -4              x -20 -24
  7. 5                  x  30
  8. 6                      x

现在选择任何索引(i, j)，其中i ≠ j，比如(0, 5)。

  1.                           j
  2. 1   2   3  -4   5   6
  3. i  1  x   2   3  -4   5   6
  4. 2      x   6  -8  10  12
  5. 3          x -12  15  18
  6. -4              x -20 -24
  7. 5                  x  30
  8. 6                      x

现在想象一下，我们想找到最佳子数组，其中i首先是第一个，然后是第二个，然后是第三个，依此类推，形成一个有效选择。在每次迭代中，我们会增加i并减少j，以便在对角线上移动：6, 10, -12，每次都将倍数添加到扩展我们选择的部分。

我们可以在每个对角线上执行此操作，以获取从(i, j)开始的最佳选择，其中i首先是第一个，然后是第二个，然后是第三个，依此类推。

现在想象一下，我们在从东北到西南的每个对角线上运行Kadane算法（直到x的地方，即i = j）。复杂度为O(n^2)时间。（在修订版本中有Python代码。）

英文:

Here's an O(n^2) time, O(1) space solution.

Lets write all O(n^2) multiples in a matrix. For example:

  1. Input {1, 2, 3, -4, 5, 6}
  2. 1   2   3  -4   5   6
  3. 1  x   2   3  -4   5   6
  4. 2      x   6  -8  10  12
  5. 3          x -12  15  18
  6. -4              x -20 -24
  7. 5                  x  30
  8. 6                      x

Now pick any indexes (i, j), i ≠ j, say (0, 5).

  1.                           j
  2. 1   2   3  -4   5   6
  3. i  1  x   2   3  -4   5   6
  4. 2      x   6  -8  10  12
  5. 3          x -12  15  18
  6. -4              x -20 -24
  7. 5                  x  30
  8. 6                      x

Now imagine we wanted to find the best subarray where i was first, then second, then third, etc. of a valid selection. In each iteration, we would increment i and decrement j, such that we move on the diagonal: 6, 10, -12, each time adding the multiple to extend our selection.

We can do this on each of the diagonals to get the best selection starting on (i, j), where i is first, then second, then third, etc.

Now imagine we ran Kadane's algorithm on each of the diagonals from northeast to southwest (up to where the xs are where i = j). Complexity O(n^2) time. (There's Python code in one of the revisions.)

答案2

得分: 2

这是代码：

  1. n = int(input())
  2. l = []
  3. res = 0
  4. l = list(map(int, input().split()))
  5. re = []
  6. while True:
  7.     if len(l) == 2:
  8.         pass
  9.         break
  10.     else:
  11.         n1 = l[1]
  12.         n2 = l[-1]
  13.         re.append(n1 * n2)
  14.         l.remove(n1)
  15.         l.remove(n2)
  16. for i in re:
  17.     res = res + i
  18. print(res)
英文:

Here is the code

  1. n=int(input())
  2. l=[]
  3. res=0
  4. l=list(map(int,input().split()))
  5. re=[]
  6. while(True):
  7. if(len(l)==2):
  8. pass
  9. break
  10. else:
  11. n1=l[1]
  12. n2=l[-1]
  13. re.append(n1*n2)
  14. l.remove(n1)
  15. l.remove(n2)
  16. for i in re:
  17. res=res+i
  18. print(res)

答案3

得分: 1

  1. #include <iostream>
  2. #include <cassert>
  3. using namespace std;
  5. template<class T> inline void umax(T &a,T b){if(a<b) a = b ; }
  6. template<class T> inline void umin(T &a,T b){if(a>b) a = b ; }
  7. template<class T> inline T abs(T a){return a>0 ? a : -a;}
  8. template<class T> inline T gcd(T a,T b){return __gcd(a, b);}
  9. template<class T> inline T lcm(T a,T b){return a/gcd(a,b)*b;}
  11. typedef long long ll;
  12. typedef pair<int, int> ii;
  13. const int inf = 1e9 + 143;
  14. const ll longinf = 1e18 + 143;
  16. inline int read()
  17. {
  18.     int x;scanf(" %d",&x);
  19.     return x;
  20. }
  22. const int N = 20001;
  23. int n;
  24. int a[N];
  26. void read_inp()
  27. {
  28.    n = read();
  29.    assert(1 <= n && n <= 20000);
  30.    for(int i = 1; i <= n; i++)
  31.    {
  32.        a[i] = read();
  33.        assert(abs(a[i]) <= int(1e6));
  34.    }
  35. }
  37. int main()
  38. {
  39. #ifdef KAZAR
  40.    freopen("f.input","r",stdin);
  41.    freopen("f.output","w",stdout);
  42.    freopen("error","w",stderr);
  43. #endif
  45.    read_inp();
  46.    ll ans = -longinf;
  47.    for(int i = 1; i <= n; i++)
  48.    {
  49.        {
  50.            int l = i - 1, r = i;
  51.            ll best = 0ll, cur = 0ll;
  52.            while(l >= 1 && r <= n)
  53.            {
  54.                ll val = (ll)a[l] * a[r];
  55.                cur += val;
  56.                umin(best, cur);
  57.                umax(ans, cur - best);
  58.                --l;
  59.                ++r;
  60.            }
  61.        }
  63.        {
  64.            int l = i - 1, r = i + 1;
  65.            ll best = 0ll, cur = 0ll;
  66.            while(l >= 1 && r <= n)
  67.            {
  68.                ll val = (ll)a[l] * a[r];
  69.                cur += val;
  70.                umin(best, cur);
  71.                umax(ans, cur - best);
  72.                --l;
  73.                ++r;
  74.            }
  75.        }
  76.    }
  77.    printf("%lld\n",ans);
  78.    return 0;
  79. }
英文: 
  1.     
  2. #include &lt;iostream&gt;
  3. #include &lt;cassert&gt;
  4. using namespace std;
  5. template&lt;class T&gt; inline void umax(T &amp;a,T b){if(a&lt;b) a = b ; }
  6. template&lt;class T&gt; inline void umin(T &amp;a,T b){if(a&gt;b) a = b ; }
  7. template&lt;class T&gt; inline T abs(T a){return a&gt;0 ? a : -a;}
  8. template&lt;class T&gt; inline T gcd(T a,T b){return __gcd(a, b);}
  9. template&lt;class T&gt; inline T lcm(T a,T b){return a/gcd(a,b)*b;}
  10. typedef long long ll;
  11. typedef pair&lt;int, int&gt; ii;
  12. const int inf = 1e9 + 143;
  13. const ll longinf = 1e18 + 143;
  14. inline int read()
  15. {
  16. int x;scanf(&quot; %d&quot;,&amp;x);
  17. return x;
  18. }
  19. const int N = 20001;
  20. int n;
  21. int a[N];
  22. void read_inp()
  23. {
  24. n = read();
  25. assert(1 &lt;= n &amp;&amp; n &lt;= 20000);
  26. for(int i = 1; i &lt;= n; i++)
  27. {
  28. a[i] = read();
  29. assert(abs(a[i]) &lt;= int(1e6));
  30. }
  31. }
  32. int main()
  33. {
  34. #ifdef KAZAR
  35. freopen(&quot;f.input&quot;,&quot;r&quot;,stdin);
  36. freopen(&quot;f.output&quot;,&quot;w&quot;,stdout);
  37. freopen(&quot;error&quot;,&quot;w&quot;,stderr);
  38. #endif
  39. read_inp();
  40. ll ans = -longinf;
  41. for(int i = 1; i &lt;= n; i++)
  42. {
  43. {
  44. int l = i - 1, r = i;
  45. ll best = 0ll, cur = 0ll;
  46. while(l &gt;= 1 &amp;&amp; r &lt;= n)
  47. {
  48. ll val = (ll)a[l] * a[r];
  49. cur += val;
  50. umin(best, cur);
  51. umax(ans, cur - best);
  52. --l;
  53. ++r;
  54. }
  55. }
  56. {
  57. int l = i - 1, r = i + 1;
  58. ll best = 0ll, cur = 0ll;
  59. while(l &gt;= 1 &amp;&amp; r &lt;= n)
  60. {
  61. ll val = (ll)a[l] * a[r];
  62. cur += val;
  63. umin(best, cur);
  64. umax(ans, cur - best);
  65. --l;
  66. ++r;
  67. }
  68. }
  69. }
  70. printf(&quot;%lld\n&quot;,ans);
  71. return 0;
  72. }

答案4

得分: -1

以下是代码的翻译部分：

  1. int main(){
  3.     int n;
  4.     cin >> n;
  5.     int arr[n];
  6.     for(int i = 0; i < n; i++) 
  7.         cin >> arr[i];
  8.     int dp[n][n];
  9.     for(int i = 0; i < n; i++)
  10.     {
  11.         for(int j = 0; j < n; j++)
  12.         {
  14.             if(j == i) 
  15.                 dp[i][j] = 0;
  16.             else if(j < i)
  17.                 dp[i][j] = 0;
  18.             else 
  19.                 dp[i][j] = arr[i] * arr[j];
  20.         }
  22.     }
  23.     cout << endl;
  24.     for(int i = 0; i < n; i++)
  25.     {
  26.         for(int j = 0; j < n; j++)
  27.             cout << dp[i][j] << "   ";
  28.         cout << endl;
  29.     }
  31.     cout << endl;
  32.     //find max sum diagonal
  33.     long long int global_sum = 0;
  34.    
  35.     //get sum of diagonal increasing i
  36.     for(int i = 0; i < n; i++)
  37.     {
  38.         long long int curr_sum = 0;
  39.         int j = i;
  40.         int k = n - 1;
  41.         while(k >= 0 && j < n){
  42.             curr_sum += dp[j][k];
  43.             k--;
  44.             j++;
  45.         }
  46.         if(curr_sum > global_sum) global_sum = curr_sum;
  48.     }
  49.     //get sum with decreasing i
  50.     for(int i = n - 1; i >= 0; i--){
  51.         long long int curr_sum = 0;
  52.         int j = i;
  53.         int k = 0;
  54.         while(k < n && j >= 0){
  55.             curr_sum += dp[j][k];
  56.             j--;
  57.             k++;
  58.         }
  59.         if(curr_sum > global_sum) global_sum = curr_sum;
  60.     }
  61.     cout << global_sum;
  62. }

请注意，此翻译仅包括代码部分，不包括任何问题或其他附加内容。如果您有其他需要翻译的内容，请继续提供。

英文:

Here is the code

  1. int main(){
  2. int n;
  3. cin&gt;&gt;n;
  4. int arr[n];
  5. for(int i=0;i&lt;n;i++) 
  6. cin&gt;&gt;arr[i];
  7. int dp[n][n];
  8. for(int i=0;i&lt;n;i++)
  9. {
  10. for(int j=0;j&lt;n;j++)
  11. {
  12. if(j==i) 
  13. dp[i][j]=0;
  14. else if(j&lt;i)
  15. dp[i][j]=0;
  16. else 
  17. dp[i][j]=arr[i]*arr[j];
  18. }
  19. }
  20. cout&lt;&lt;endl;
  21. for(int i=0;i&lt;n;i++)
  22. {
  23. for(int j=0;j&lt;n;j++)
  24. cout&lt;&lt;dp[i][j]&lt;&lt;&quot;   &quot;;
  25. cout&lt;&lt;endl;
  26. }
  27. cout&lt;&lt;endl;
  28. //find max sum diagonal
  29. long long int global_sum=0;
  30. //get sum of diagonal increasing i
  31. for(int i=0;i&lt;n;i++)
  32. {
  33. long long int curr_sum=0;
  34. int j=i;
  35. int k=n-1;
  36. while(k&gt;=0 &amp;&amp; j&lt;n){
  37. curr_sum+=dp[j][k];
  38. k--;
  39. j++;
  40. }
  41. if(curr_sum&gt;global_sum) global_sum=curr_sum;
  42. }
  43. //get sum with decreasing i
  44. for(int i=n-1;i&gt;=0;i--){
  45. long long int curr_sum=0;
  46. int j=i;
  47. int k=0;
  48. while(k&lt;n &amp;&amp; j&gt;=0){
  49. curr_sum+=dp[j][k];
  50. j--;
  51. k++;
  52. }
  53. if(curr_sum&gt;global_sum) global_sum=curr_sum;
  54. }
  55. cout&lt;&lt;global_sum;}

This code passes the testcase you gave and other testcases i tried myself. Its O(n^2) complexity.

huangapple
  • 本文由 发表于 2020年10月25日 23:05:59
  • 转载请务必保留本文链接：https://go.coder-hub.com/64525220.html
  • algorithm
  • java
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定