DOMAIN CAMP
Student Name: Harwinder Kaur
UID: 20BCS1714
Group: G-26
Subject: Java
Problem 1: Maximum Subarray Sum
Given an array of integers, find the contiguous subarray with the largest sum. Write a Java
program that takes an array as input and outputs the maximum subarray sum.
Sample Input:
Array: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Sample Output:
Maximum Subarray Sum: 6 (corresponding to the subarray [4, -1, 2, 1])
SOLUTION:
public class MaximumSubarraySum {
public static int findMaximumSubarraySum(int[] nums) {
int currentSum = nums[0];
int maxSum = nums[0];
for (int i = 1; i < [Link]; i++) {
// Calculate the maximum of the current element or the sum of the current element and the
previous subarray sum
currentSum = [Link](nums[i], currentSum + nums[i]);
// Update the maximum sum if the current sum is larger
maxSum = [Link](maxSum, currentSum);
return maxSum;
}
public static void main(String[] args) {
int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
int maxSubarraySum = findMaximumSubarraySum(nums);
[Link]("Maximum Subarray Sum: " + maxSubarraySum);
Problem 2: Longest Increasing Subsequence
Given an array of integers, find the length of the longest increasing subsequence. Write a
Java program that takes an array as input and outputs the length of the longest increasing
subsequence.
Sample Input:
Array: [10, 22, 9, 33, 21, 50, 41, 60]
Sample Output:
Length of Longest Increasing Subsequence: 5 (corresponding to the subsequence [10, 22,
33, 50, 60])
SOLUTION:
public class LongestIncreasingSubsequence {
public static int findLongestIncreasingSubsequenceLength(int[] nums) {
int n = [Link];
int[] dp = new int[n];
dp[0] = 1;
int maxLength = 1;
for (int i = 1; i < n; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = [Link](dp[i], dp[j] + 1);
maxLength = [Link](maxLength, dp[i]);
return maxLength;
public static void main(String[] args) {
int[] nums = {10, 22, 9, 33, 21, 50, 41, 60};
int longestIncreasingSubsequenceLength = findLongestIncreasingSubsequenceLength(nums);
[Link]("Length of Longest Increasing Subsequence: " +
longestIncreasingSubsequenceLength);
Problem3: Sudoku Solver
Write a Java program that solves a given Sudoku puzzle. The Sudoku puzzle consists of a
9x9 grid, divided into nine 3x3 sub-grids. Each cell in the grid can contain a digit from 1 to 9.
The objective is to fill the grid in such a way that every row, every column, and every 3x3
sub-grid contains all the digits from 1 to 9 without repetition.
The program should take a partially filled Sudoku grid as input, with empty cells represented
by 0, and solve it by filling in the missing digits.
Sample Input:
Grid:
530070000
600195000
098000060
800060003
400803001
700020006
060000280
000419005
000080079
Sample Output:
Solution:
534678912
672195348
198342567
859761423
426853791
713924856
961537284
287419635
345286179
SOLUTION:
public class SudokuSolver {
private static final int SIZE = 9;
public static boolean solveSudoku(int[][] grid) {
int row = -1;
int col = -1;
boolean isEmpty = true;
// Find the first empty cell
for (int i = 0; i < SIZE; i++) {
for (int j = 0; j < SIZE; j++) {
if (grid[i][j] == 0) {
row = i;
col = j;
isEmpty = false;
break;
}
}
if (!isEmpty) {
break;
// If there are no empty cells, the puzzle is solved
if (isEmpty) {
return true;
// Try different numbers in the empty cell
for (int num = 1; num <= SIZE; num++) {
if (isSafe(grid, row, col, num)) {
grid[row][col] = num;
// Recursively solve the puzzle
if (solveSudoku(grid)) {
return true;
// If the current configuration doesn't lead to a solution, backtrack
grid[row][col] = 0;
return false;
public static boolean isSafe(int[][] grid, int row, int col, int num) {
// Check if the number already exists in the same row
for (int i = 0; i < SIZE; i++) {
if (grid[row][i] == num) {
return false;
// Check if the number already exists in the same column
for (int i = 0; i < SIZE; i++) {
if (grid[i][col] == num) {
return false;
// Check if the number already exists in the same 3x3 sub-grid
int subGridStartRow = row - row % 3;
int subGridStartCol = col - col % 3;
for (int i = subGridStartRow; i < subGridStartRow + 3; i++) {
for (int j = subGridStartCol; j < subGridStartCol + 3; j++) {
if (grid[i][j] == num) {
return false;
return true;
public static void printGrid(int[][] grid) {
for (int i = 0; i < SIZE; i++) {
for (int j = 0; j < SIZE; j++) {
[Link](grid[i][j] + " ");
}
[Link]();
public static void main(String[] args) {
int[][] grid = {
{5, 3, 0, 0, 7, 0, 0, 0, 0},
{6, 0, 0, 1, 9, 5, 0, 0, 0},
{0, 9, 8, 0, 0, 0, 0, 6, 0},
{8, 0, 0, 0, 6, 0, 0, 0, 3},
{4, 0, 0, 8, 0, 3, 0, 0, 1},
{7, 0, 0, 0, 2, 0, 0, 0, 6},
{0, 6, 0, 0, 0, 0, 2, 8, 0},
{0, 0, 0, 4, 1, 9, 0, 0, 5},
{0, 0, 0, 0, 8, 0, 0, 7, 9}
};
if (solveSudoku(grid)) {
[Link]("Solution:");
printGrid(grid);
} else {
[Link]("No solution exists.");