Map*_*pan 4 java arrays algorithm
我一直在玩一些算法,以获得最大的总和,而阵列中没有两个相邻的元素,但我在想:
如果我们有一个包含n个元素的数组,并且我们想要找到最大的总和,那么3个元素永远不会触及.也就是说如果我们有数组a = [2,5,3,7,8,1]我们可以选择2和5而不是2,5和3,因为那时我们连续3个.这个数组的这些规则的总和将是:22(2和5,7和8. 2 + 5 + 7 + 8 = 22)
我不确定如何实现这个,任何想法？
编辑:
我只是想到可能会做的事情:
让我们坚持使用相同的数组:
int[] a = {2, 5, 3, 7, 8, 1};
int{} b = new int[n}; //an array to store results in
int n = a.length;
// base case
b[1] = a[1];
// go through each element:
for(int i = 1; i < n; i++)
{
/* find each possible way of going to the next element
use Math.max to take the "better" option to store in the array b*/
}
return b[n]; // return the last (biggest) element.
这只是我想到的一个想法,没有达到这个时间.
最大和的算法使得没有两个元素相邻:
arr []中所有元素的循环并保持两个和,包括和excl其中incl =包括前一个元素的最大和和excl =不包括前一个元素的最大和.
除当前元素之外的最大总和将是max(incl,excl),并且包括当前元素的最大和将是excl + current元素(注意,仅考虑excl,因为元素不能相邻).
在循环结束时返回最大值incl和excl.
执行:
#include<stdio.h>
/*Function to return max sum such that no two elements
are adjacent */
int FindMaxSum(int arr[], int n)
{
int incl = arr[0];
int excl = 0;
int excl_new;
int i;
for (i = 1; i < n; i++)
{
/* current max excluding i */
excl_new = (incl > excl)? incl: excl;
/* current max including i */
incl = excl + arr[i];
excl = excl_new;
}
/* return max of incl and excl */
return ((incl > excl)? incl : excl);
}
/* Driver program to test above function */
int main()
{
int arr[] = {5, 5, 10, 100, 10, 5};
printf("%d \n", FindMaxSum(arr, 6));
getchar();
return 0;
}
时间复杂度:O(n)
空间复杂度:O(1)
编辑1:
如果您理解上述代码,我们可以通过维护先前位置的已相邻数字的数量来轻松解决此问题.这是对所需问题的有效实施
//We could assume we store optimal result upto i in array sum
//but we need only sum[i-3] to sum[i-1] to calculate sum[i]
//so in this code, I have instead maintained 3 ints
//So that space complexity to O(1) remains
#include<stdio.h>
int max(int a,int b)
{
if(a>b)
return 1;
else
return 0;
}
/*Function to return max sum such that no three elements
are adjacent */
int FindMaxSum(int arr[], int n)
{
int a1 = arr[0]+arr[1];//equivalent to sum[i-1]
int a2 =arr[0];//equivalent to sum[i-2]
int a3 = 0;//equivalent to sum [i-3]
int count=2;
int crr = 0;//current maximum, equivalent to sum[i]
int i;
int temp;
for (i = 2; i < n; i++)
{
if(count==2)//two elements were consecutive for sum[i-1]
{
temp=max(a2+arr[i],a1);
if(temp==1)
{
crr= a2+arr[i];
count = 1;
}
else
{
crr=a1;
count = 0;
}
//below is the case if we sould have rejected arr[i-2]
// to include arr[i-1],arr[i]
if(crr<(a3+arr[i-1]+arr[i]))
{
count=2;
crr=a3+arr[i-1]+arr[i];
}
}
else//case when we have count<2, obviously add the number
{
crr=a1+arr[i];
count++;
}
a3=a2;
a2=a1;
a1=crr;
}
return crr;
}
/* Driver program to test above function */
int main()
{
int arr[] = {2, 5, 3, 7, 8, 1};
printf("%d \n", FindMaxSum(arr, 6));
return 0;
}
时间复杂度:O(n)
空间复杂度:O(1)
adi的解决方案可以很容易地推广,以允许最多n个相邻元素包含在总和中.关键是要保持的阵列Ñ + 1种元素,其中,所述ķ个阵列(0≤在元件ķ ≤ Ñ)给出最大总和假定ķ先前输入被包括在总和与ķ + 1-不是:
/**
* Find maximum sum of elements in the input array, with at most n adjacent
* elements included in the sum.
*/
public static int maxSum (int input[], int n) {
int sums[] = new int[n+1]; // new int[] fills the array with zeros
int max = 0;
for (int x: input) {
int newMax = max;
// update sums[k] for k > 0 by adding x to the old sums[k-1]
// (loop from top down to avoid overwriting sums[k-1] too soon)
for (int k = n; k > 0; k--) {
sums[k] = sums[k-1] + x;
if (sums[k] > newMax) newMax = sums[k];
}
sums[0] = max; // update sums[0] to best sum possible if x is excluded
max = newMax; // update maximum sum possible so far
}
return max;
}
与adi的解决方案一样,这个也在线性时间内运行(确切地说,O(mn),其中m是输入的长度,n是总和中允许的相邻元素的最大数量)并使用恒定的内存量独立于输入长度(O(n)).实际上,甚至可以很容易地修改它以处理其长度未提前知道的输入流.