22BCE5111
SAFEEQ AHAMED S
DAA LAB ASSIGNMENT
1) Given an integer array A, find the maximum subarray that has the largest sum and
return its sum along with its starting and ending indices. (using DCC)
Input:
n# size of the array
Array values
Output:
Maximum sum
Starting indices
Ending indices
Sample input:
9
-3
1
-8
12
0
-3
5
-9
4
Output:
14
3
6
PROGRAM:
#include<iostream>
#include<algorithm>
using namespace std;
struct SubarrayInfo
{int sum;
int start;
int end; };
SubarrayInfo crosum(int arr[], int low, int mid, int high) {
int sum = 0, lss = -1, rss = -1;
int start_index = -1, end_index = -1;
for (int i = mid; i >= low; i--)
{ sum += arr[i];
if (sum > lss)
{lss = sum;
start_index = i;}
}
sum = 0;
for (int i = mid + 1; i <= high; i++)
{ sum += arr[i];
if (rss < sum)
{rss = sum;
end_index = i;}
}
SubarrayInfo result;
result.sum = lss + rss;
result.start = start_index;
result.end = end_index;
return result;
}
SubarrayInfo mss(int arr[], int low, int high) {
if (low == high) {
SubarrayInfo result;
result.sum = arr[low];
result.start = low;
result.end = high;
return result;
}
int mid = (low + high) / 2;
SubarrayInfo left = mss(arr, low, mid);
SubarrayInfo right = mss(arr, mid + 1, high);
SubarrayInfo cross = crosum(arr, low, mid, high);
if (left.sum >= right.sum && left.sum >= cross.sum) {
return left;
} else if (right.sum >= left.sum && right.sum >= cross.sum) {
return right;
} else {
return cross;
}
}
int main() {
int n, i;
cout << "Enter the number of data elements in the array: ";
cin >> n;
int arr[n];
for (i = 0; i < n; i++) {
cout << "Enter element " << i + 1 << ": ";
cin >> arr[i];
}
SubarrayInfo result = mss(arr, 0, n - 1);
cout << "The Maximum Subarray Sum is " << result.sum<<endl
<< " with starting index " << result.start <<endl<< " and ending index " << result.end;
}
OUTPUT:
2) Construct the convexhull using the Jarvis method
PROGRAM:
#include <iostream>
#include <cmath>
#include <stack>
using namespace std;
struct Point
{int x, y;};
int orientation(Point p1, Point p2, Point p3) {
int val = (p2.y - p1.y) * (p3.x - p2.x) - (p2.x - p1.x) * (p3.y - p2.y);
if (val == 0) return 0;
return (val > 0) ? 1 : 2;
}
int nextPoint(Point points[], int current, int n) {
int next = (current + 1) % n;
for (int i = 0; i < n; i++) {
if (orientation(points[current], points[i], points[next]) == 2)
next = i;
}
return next;
}
void convexHull(Point points[], int n) {
if (n < 3) return;
// Find the leftmost point
int leftmost = 0;
for (int i = 1; i < n; i++) {
if (points[i].x < points[leftmost].x)
leftmost = i;
}
int current = leftmost;
stack<Point> hull;
do {
hull.push(points[current]);
int next = nextPoint(points, current, n);
current = next;
} while (current != leftmost);
// Print the convex hull points
cout << "Convex Hull Points:" << endl;
while (!hull.empty()) {
Point p = hull.top();
cout << "(" << p.x << ", " << p.y << ")" << endl;
hull.pop();
}
}
int main() {
Point points[] = { { 0, 0 }, { 7, 0 }, { 3, 1 }, { 5, 2 }, { 9, 6 }, { 3, 3 }, { 5, 5 }, { 1, 4 } };
int n = sizeof(points) / sizeof(points[0]);
convexHull(points, n);
return 0;
}
OUTPUT:
3) You have a list of N jobs, each with its own deadline and profit. The profit is only earned if the
job is finished before its deadline. Your goal is to find the maximum profit possible and the total
number of jobs completed. Each job takes one unit of time, and only one job can be done at a
time. Use greedy approach to solve the problem.
Input:
No of jobs, deadline of each job and its profit.
Deadline
Output:
Total number of jobs completed
Maximum profit
Job completion order
PROGRAM:
#include <iostream>
#include <algorithm>
using namespace std;
struct Job {
int id;
int deadline;
int profit;
};
bool compare(Job a, Job b) {
return a.profit > b.profit;
}
void findMaxProfit(Job jobs[], int n) {
sort(jobs, jobs + n, compare);
int maxDeadline = 0;
for (int i = 0; i < n; i++) {
maxDeadline = max(maxDeadline, jobs[i].deadline);
}
int slots[maxDeadline] = {0};
int completedJobs = 0;
int maxProfit = 0;
int jobCompletionOrder[n];
for (int i = 0; i < n; i++) {
int deadline, profit;
cout << "Enter deadline and profit for job " << i + 1 << ": ";
cin >> deadline >> profit;
jobs[i].deadline = deadline;
jobs[i].profit = profit;
int slot = deadline - 1;
while (slot >= 0 && slots[slot] != 0) {
slot--;
}
if (slot >= 0) {
slots[slot] = jobs[i].id;
completedJobs++;
jobCompletionOrder[completedJobs - 1] = jobs[i].id;
maxProfit += profit;
}
}
cout << "Total number of jobs completed: " << completedJobs << endl;
cout << "Maximum profit: " << maxProfit << endl;
cout << "Job completion order: ";
for (int i = 0; i < completedJobs; i++) {
cout << jobCompletionOrder[i] << " ";
}
cout << endl;
}
int main() {
int n;
cout << "Enter the number of jobs: ";
cin >> n;
Job jobs[n];
for (int i = 0; i < n; i++) {
jobs[i].id = i + 1;
}
findMaxProfit(jobs, n);
return 0;
}
OUTPUT:
