Language: C++ Let us say the values are arranged in two dimensional array instea
ID: 3804409 • Letter: L
Question
Language: C++
Let us say the values are arranged in two dimensional array instead. The thief wants to start anywhere, pick up a series of items (by going up, down, left or right after picking up each item) and hopes for the total to match the target value. Here are a few examples using 4x4 array. Items in GREEN are selected & they total to specified target value in each case. 15 10 44 19 Target: 77 91 7 24 21 17 9 1 45 3 9 67 32 15 10 4 19 Target: 64 91 7 24 21 9 17 1 45 3 9 67 32 Target: 61 15 10 4 19 91 7 24 21 9 17 1 45 3 9 67 32 15 10 4 19 Target: 141 91 7 24 21 9 17 1 45 3 9 67 32 int n int values n x n arrayExplanation / Answer
Here is the code for above scenario:
#include <stdio.h>
#include <string.h>
#include <limits.h>
#define ROW 4
#define COL 5
// Implementation of Kadane's algorithm for 1D array. The function
// returns the maximum sum and stores starting and ending indexes of the
// maximum sum subarray at addresses pointed by start and finish pointers
// respectively.
int kadane(int* arr, int* start, int* finish, int n)
{
// initialize sum, maxSum and
int sum = 0, maxSum = INT_MIN, i;
// Just some initial value to check for all negative values case
*finish = -1;
// local variable
int local_start = 0;
for (i = 0; i < n; ++i)
{
sum += arr[i];
if (sum < 0)
{
sum = 0;
local_start = i+1;
}
else if (sum > maxSum)
{
maxSum = sum;
*start = local_start;
*finish = i;
}
}
// There is at-least one non-negative number
if (*finish != -1)
return maxSum;
// Special Case: When all numbers in arr[] are negative
maxSum = arr[0];
*start = *finish = 0;
// Find the maximum element in array
for (i = 1; i < n; i++)
{
if (arr[i] > maxSum)
{
maxSum = arr[i];
*start = *finish = i;
}
}
return maxSum;
}
// The main function that finds maximum sum rectangle in M[][]
void findMaxSum(int M[][COL])
{
// Variables to store the final output
int maxSum = INT_MIN, finalLeft, finalRight, finalTop, finalBottom;
int left, right, i;
int temp[ROW], sum, start, finish;
// Set the left column
for (left = 0; left < COL; ++left)
{
// Initialize all elements of temp as 0
memset(temp, 0, sizeof(temp));
// Set the right column for the left column set by outer loop
for (right = left; right < COL; ++right)
{
// Calculate sum between current left and right for every row 'i'
for (i = 0; i < ROW; ++i)
temp[i] += M[i][right];
// Find the maximum sum subarray in temp[]. The kadane()
// function also sets values of start and finish. So 'sum' is
// sum of rectangle between (start, left) and (finish, right)
// which is the maximum sum with boundary columns strictly as
// left and right.
sum = kadane(temp, &start, &finish, ROW);
// Compare sum with maximum sum so far. If sum is more, then
// update maxSum and other output values
if (sum > maxSum)
{
maxSum = sum;
finalLeft = left;
finalRight = right;
finalTop = start;
finalBottom = finish;
}
}
}
// Print final values
printf("(Top, Left) (%d, %d) ", finalTop, finalLeft);
printf("(Bottom, Right) (%d, %d) ", finalBottom, finalRight);
printf("Max sum is: %d ", maxSum);
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.